【字符串】ExKMP、SA、SAM、自动机
NanoApe
posted @ 2016年2月17日 19:21
in 蒟蒻不撕烤智熵何来
, 1625 阅读
ExKMP
求模式串和主串的每一个后缀的最长公共前缀
1 2 3 4 5 6 7 8 9 | 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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)
