【字符串】ExKMP、SA、SAM、自动机
NanoApe
posted @ 2016年2月17日 19:21
in 蒟蒻不撕烤智熵何来
, 1725 阅读
ExKMP
求模式串和主串的每一个后缀的最长公共前缀
int k, p;
n[0] = l*2; /*n[0] = l;*/ n[1] = 0; while (s[n[1]] == s[n[1]+1]) n[1]++;
p = n[k=1]+1;
rep(i, 2, l-1)
{
n[i] = i<p ? min(p-i, n[i-k]) : 0;
while (s[n[i]] == s[n[i]+i]) n[i]++;
if (i+n[i]>p) p = i+n[i], k = i;
}
SAM
int cn, now, ch[maxn][26], F[maxn], d[maxn];
inline int Copy(int p, int c)
{
int x=++cn, y=ch[p][c];
d[x]=d[p]+1; rep(i, 0, 25) ch[x][i]=ch[y][i]; F[x]=F[y]; F[y]=x;
while (~p && ch[p][c]==y) ch[p][c]=x, p=F[p];
return x;
}
inline void Add(int c)
{
int p,o; if ((p=ch[now][c]))
{
if (d[now]+1!=d[p]) Copy(now,c);
now=ch[now][c];
}
else
{
d[o=++cn]=d[now]+1; p=now; now=o;
while (~p && !ch[p][c]) ch[p][c]=o, p=F[p];
F[o]=~p?(d[p]+1==d[ch[p][c]]?ch[p][c]:Copy(p,c)):0;
}
}
评论 (0)
NanoApe
ENE>.<~
计数器
165625
分类
搜索
听听看？
最新留言
最新评论
链接
RSS
