NanoApe's Blog

既是咸鱼又是辣鸡

【字符串】ExKMP、SA、SAM、自动机

NanoApe posted @ 2016年2月17日 19:21 in 蒟蒻不撕烤智熵何来 , 519 阅读

 

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;
	}
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter