后缀数组

发表于 | 分类于 | 阅读次数:

##简介
后缀数组（Suffix Array, SA）是一种在字符串问题中很实用的工具，其主要作用是求多模板匹配和最长公共前缀（LCP）。与 AC自动机 预先处理模板串不同，后缀数组在进行多模板匹配的是预处理文本串。
##模板
后缀数组的构造方法主要有三个： 哈希、倍增、DC3。
其中哈希是近似算法，方便写，虽然不能保证绝对正确但效果还是比较好的；哈希和DC3都是线性时间复杂度的，而倍增算法则是 $O(Mlog_2N) ,\text{M:字符集长度;N:串长}$ ,不过由于 DC3 难于理解，不太实用，本篇文章将不会涉及。
###Hash
比较好理解，不过写起来根倍增难度不相上下，而倍增可以保证绝对正确，非洲人就不要用此方法了

代码系转载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ULL;
const ULL BASE=127;
const int MAXN=6000000;
ULL base[MAXN],hash[MAXN];
int len;
char s[MAXN];
inline ULL get_hash(int l,int r)
{
    return hash[r]-hash[l-1]*base[r-l+1];
}
struct S{int pos;}suf[MAXN];
inline int find(int l,int r,int f1,int f2)
{
    if(l+1>=r)
    {
        if(get_hash(f1,f1+r-1)==get_hash(f2,f2+r-1)) return r;
        else return l;
    }
    int mid=(l+r)>>1;
    if(get_hash(f1,f1+mid-1)==get_hash(f2,f2+mid-1)) return find(mid,r,f1,f2);
    else return find(l,mid-1,f1,f2);
}
inline bool cmp(const S & x,const S & y)
{
    int len1=len-x.pos+1,len2=len-y.pos+1;
    int maxx=find(0,min(len1,len2)+1,x.pos,y.pos);
    if(maxx==min(len1,len2)+1) return x.pos>y.pos;
    else return s[x.pos+maxx]<s[y.pos+maxx];
}
int sa[maxn],rank[maxn],height[maxn];
int main()
{
    freopen("makedata.out","r",stdin);
    freopen("mine.out","w",stdout);
    scanf("%s",s+1); len=strlen(s+1);
    base[0]=1; for(int i=1;i<=len;i++) base[i]=base[i-1]*BASE;
    for(int i=1;i<=len;i++) hash[i]=hash[i-1]*BASE+s[i]-'a'+1;
    for(int i=1;i<=len;i++) suf[i].pos=i;
    sort(suf+1,suf+len+1,cmp);
    for(int i=1;i<=len;i++)
    {
        rank[suf[i].pos]=i;
        sa[i]=suf[i].pos;
    }
    for(int i=2;i<=len;i++)
    {
        int len1=len-sa[i-1]+1,len2=len-sa[i]+1;
        height[i]=find(0,min(len1,len2),sa[i-1],sa[i]);
    }
    for(int i=1;i<=len;i++)
        printf("%d %d\n",sa[i],height[i]);
    return 0;
}

###倍增
首先直观地看一下算法过程：
例

其实就是将一个字符串的所有后缀按照字典序排序，在排序的过程中我们用了倍增的方法依据两个关键字进行排序，直到没有并列的为止。

要理解此过程，需要了解基数排序的相关知识。

时间复杂度：$O(Mlog_2N)$
####buildSA 函数
| 变量名 | 解释 |
| :—: | :—————– |
| sa | 后缀数组，即排序后的数组序列 |
| t1,t2 | 储存用，通过 x,y 调用 |
| x,y | 两个排序关键字 |
| na | 串本体 |
| n | 串长 |
| m | 传入时为字符集长度，实际上是桶的上限 |

过程：

1. 基数排序初始化第一关键字，并初步计算后缀数组 (8~11)
2. 倍增过程：
3. 依照之前的 sa 求出第二关键字
 4. 基数排序求出第一关键字，并更新后缀数组
 5. 利用第一关键字和 sa 求出新的第一关键字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXN];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}

####calHt (calculate Height) 函数
| 变量名 | 解释 |
| :–: | :————————— |
| rk | rank，从 i 起始的后缀在后缀数组的排名 |
| ht | height，sa[i] 与 sa[i-1] 的 LCP |
过程：

1. 根据求出的 sa 数组求每个后缀的排名
2. 求每个后缀的 height

求 rank 的过程没什么技术含量，主要是求 height 的过程不好理解

如果使用朴算法计算 height 数组的话，那么时间复杂度会达到 $O(N^2)$ ，这样，我们对前面计算 sa 数组的优化求前功尽弃了，所以我们需要对 height 数组的计算过程进行优化。其实，优化的作用是很明显的，最终复杂度可以达到 $O(N)$ 。

优化的主要依据就是以下定理：
$$height[rank[i]]\geq height[rank[i]-1]-1$$

1
2
3
4
5
6
7
8
9
10
11
12
13
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}

##应用
###最长公共前缀
最长公共前缀是众多解决后缀数组问题的基础。

我们之前已经求出了 height 数组，即 rank 相邻的两个后缀的 LCP ，经过一系列推理，我们可以得到以下结论：

对于后缀 $i,j$ ，有 $$LCP(i,j)=Min_{\ i<k\leq j}{height[rank[k]]}$$

有了这个定理后，我们就能利用 ST 求 RMQ 的方法求 LCP 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct ST
{
	int f[MAXN][32];
	void init(int * na,int len)
	{
		int i,k;
		for(i=1;i<=len;i++) f[i][0]=na[i];
		for(j=1;(1<<k)<=len;k++)
			for(i=1;i+(1<<k)-1<=len;i++)
				f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
	int calRMQ(int l, int r)
	{
		int j=log(r-l+1)/log(2);
		return min(f[l][j],f[r+1-(1<<j)][j]);
	}
} st;

int calLCP(int x,int y)
{
	x=rk[x],y=rk[y];
	if(x>y) swap(x,y);
	return st.calRMQ(x+1,y);
}

###单个串问题
####重复子串
最长可重叠最长重复子串问题

很明显，只需要求出 height 数组中的最大值即可。

最长不可重复最长重复子串问题
[POJ1743] Musical Theme

二分答案，二分 k ，判断是否存在长度为 k 的子串是相同的，且不重叠。

这里出现了一个重要的思想：分组

分组的原则就是若一个后缀的 i 的 $height[i]<2$ ，那么将它分到一个新组里。这样分组的意义就在于让最长公共前缀不小于 k 的两个后缀分在同一组内。

接下来，我们需要判断是否存在不重叠的，方法很简单，我们对于每一个分组，求出其 sa[i] 的极差，如过有一个分组的极差大于等于 k ，则成立，反之则不成立。

时间复杂度： $O(Nlog_2N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=2e4+5;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXN];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}

bool check(int n,int k)
{
	int i,l=sa[1],r=sa[1];
	for(i=2;i<=n;i++)
	{
		if(ht[i]<k) l=r=sa[i];
		else
		{
			l=min(l,sa[i]),r=max(r,sa[i]);
			if(r-l+1>=k) return true;
		}
	}
	return false;
}

int na[MAXN];
int main()
{
	int n,i,la,rc;
	while(scanf("%d",&n)&&n)
	{
		n--;
		scanf("%d",&la);
		for(i=0;i<n;i++)
		{
			scanf("%d",&rc);
			na[i]=rc-la+100;
			la=rc;
		}
		na[n]=0;
		buildSA(na,n+1,200);
		calHt(na,n);
		int l=1,r=n>>1,mid;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(check(n,mid)) l=mid+1;
			else r=mid-1;
		}
		int ans=r+1;
		printf("%d\n",ans>=5?ans:0);
	}
}

最长可重叠 k 次重复子串问题
[POJ3261] Mikl Pattern

本题可以沿袭上一题的二分答案分组做法，判断有没有一个分组的后缀个数大于等于 k ，有的话就成立了。

时间复杂度： $O(Nlog_2N)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=2e4+5,MAXM=1e6+5;

int N,K;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXM];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}
bool check(int x,int n)
{
    int i,cnt=1;
    for(i=1;i<=n;i++)
	    if(ht[i]>=x)
	    {
			cnt++;
		    if(cnt>=K) return true;
	    }
    	else cnt=1;
    return false;
}
int na[MAXN];
int main()
{
	int i;
	scanf("%d%d",&N,&K);
	for(i=0;i<N;i++) scanf("%d",&na[i]),na[i]++;
	na[N]=0;
	buildSA(na,N+1,MAXM);
	calHt(na,N);
	int l=1,r=N,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid,N)) l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
	return 0;
}

####子串个数问题
不相同的子串个数
[SPOJ705] New Distinct Substrings

我们能够推出：一个长度为 $n$ 的串有 $n\times(n+1)\div2$ 个子串，我们只要减去其中重复的即可；而其中重复的个数可以证明是 height 数组的总和。

综上所述，一个长度为 $n$ 的串中有
$$\frac{n\times(n+1)}{2}-\sum_{i=1}^nheight[i]$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;

const int MAXN=50001;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXN];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}

char s[MAXN];
int na[MAXN];
int main()
{
	int i,n,T;
	ll ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s);
		n=strlen(s);
		for(i=0;i<n;i++) na[i]=s[i];
		na[n]=0;
		buildSA(na,n+1,128);
		calHt(na,n);
		ans=(ll)n*(n+1)/2;
		for(i=1;i<=n;i++) ans-=ht[i];
		printf("%lld\n",ans);
	}
	return 0;
}

####回文子串问题
最长回文子串问题
[URAL1297] Palindrome

可以将原字符串翻过来接在原字符串后，为防止混淆，中间加一个原文中没有出现过的字符，这样，问题就变为了求新字符串中两个后缀的 LCP 长度的最大值，由于题目要求输出这个回文字符串，所以我们不能简单地统计，而需要枚举每一个位置，计算以它为中心的回文子串，然后找出最长的即可。需要注意的是，回文子串的长度可能是奇数或偶数，所以需要分两种情况计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

const int MAXN=2e3+2;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXN];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}

struct ST
{
	int f[MAXN][32];
	void init(int * na,int len)
	{
		int i,k;
		for(i=1;i<=len;i++) f[i][0]=na[i];
		for(k=1;(1<<k)<=len;k++)
			for(i=1;i+(1<<k)-1<=len;i++)
				f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
	int calRMQ(int l, int r)
	{
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r+1-(1<<k)][k]);
	}
} st;

int calLCP(int x,int y)
{
	x=rk[x],y=rk[y];
	if(x>y) swap(x,y);
	return st.calRMQ(x+1,y);
}

char s[MAXN];int na[MAXN];
int main()
{
	int i,n,len,lcp,pos,maxLcp=0;
	scanf("%s",s);len=strlen(s);
	for(i=0;i<len;i++) na[i]=s[i]; 
	na[len]=1;
	for(i=0;i<len;i++) na[i+len+1]=s[len-i-1];
	n=len*2+1;na[n]=0;
	buildSA(na,n+1,256);
	calHt(na,n);
	st.init(ht,n);
	for(i=0;i<len;i++)
	{
		lcp=calLCP(i,n-i);
		if(lcp*2>maxLcp) maxLcp=lcp*2,pos=i-lcp;
		lcp=calLCP(i,n-i-1);
		if(lcp*2-1>maxLcp) maxLcp=lcp*2-1,pos=i-lcp+1;
	}
	s[pos+maxLcp]=0;
	printf("%s\n",s+pos);
	return 0;
}

####连续重复子串问题
全覆盖型子串连续重复最大次数问题
[POJ2406] Power Strings

此类题不难处理，枚举重复多次的字符串的长度 $k$，先把不能整除整个字符串长度 $n$ 的情况排除掉，然后判断 $LCP(0,k)=n-k$ 是否成立，成立的话就可以了。这里由于我们求 LCP 时要求的 RMQ 问题的一个端点是固定的，所以可以直接 $O(N)$ 初始化一下，不需要稀疏表预处理。

然而这道题目由于数据达到了 $10^6$ 要求使用 $O(N)$ 的算法， $O(Nlog_2N)$ 的倍增算法会 TLE ，用 DC3 倒是可以过。其实本题是一道 KMP 裸题，此处只是开拓一下思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=1e6+5,MAXM=1e3+5;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXM];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}

int rmq[MAXN];
inline void calRMQ(int n)
{
	int i,mid=rk[0];
	for(i=mid-1;i>=1;i--) 
		rmq[i]=i==mid-1?ht[mid]:min(rmq[i+1],ht[i+1]);
	for(i=mid+1;i<=n;i++) 
		rmq[i]=i==mid+1?ht[mid]:min(rmq[i-1],ht[i-1]);
}

char s[MAXN];
int na[MAXN];
int main()
{
	freopen("data.in","r",stdin);
	while(~scanf("%s",s))
	{
		if(s[0]=='.') break;
		int i,k,len=strlen(s);
		for(i=0;i<len;i++) na[i]=s[i];
		na[len]=0;
		buildSA(na,len+1,256);
		calHt(na,len);
		calRMQ(len);
		for(k=1;k<=len;k++)
			if(len%k==0)
				if(rmq[rk[k]]==len-k)
				{
					printf("%d\n",len/k);
					break;
				}
	}
	return 0;
}

重复次数最多的连续重复子串问题
[SPOJ687] Repeats

先枚举长度 k ,求长度为 k 的子串最多能连续出现多少次。记这个子字符串为 s ，那么 s 一定包含 $na[1\times k],\ na[2\times k],\ na[3\times k],\ \dots$ 中某相邻的两个。那么只需求 $LCP(ik,(i+1)k)$ ，然后判断是否在这两个位置前面能够匹配一次 s ，若可以，答案加一，最后再讲答案加一即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

const int MAXN=5e4+5,MAXM=300;

int sa[MAXN];
int t1[MAXN],t2[MAXN],c[MAXN];
int isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	for(i=0;i<m;i++) c[i]=0;
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=1,p=1;p<n;j<<=1,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<m;i++) c[i]=0;
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}
struct ST
{
	int f[MAXN][32];
	void init(int * na,int len)
	{
		int i,k;
		for(i=1;i<=len;i++) f[i][0]=na[i];
		for(k=1;(1<<k)<=len;k++)
			for(i=1;i+(1<<k)-1<=len;i++)
				f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
	}
	int calRMQ(int l, int r)
	{
		int k=log(r-l+1)/log(2);
		return min(f[l][k],f[r+1-(1<<k)][k]);
	}
} st;

int calLCP(int x,int y)
{
	x=rk[x],y=rk[y];
	if(x>y) swap(x,y);
	return st.calRMQ(x+1,y);
}

int na[MAXN];
int main()
{
	int T,n;scanf("%d",&T);
	while(T--)
	{
		int i,j,k;char c;
		scanf("%d",&n);
		for(i=0;i<n;i++) 
		{do c=getchar();while(c==' '||c=='\n');na[i]=c;}
		na[n]=0;
		buildSA(na,n+1,256);
		calHt(na,n);
		st.init(ht,n);
		int ans=0,rans;
		for(i=1;i<n;i++)//len
			for(j=0;j+i<n;j+=i)//pos
			{
				k=calLCP(j,j+i);
				rans=k/i;
				int lpos=j-(i-k%i);
				if(lpos>=0)
					if(calLCP(lpos,lpos+i)>=i-k%i) rans++;
				if(rans>ans) ans=rans;
			}
		printf("%d\n",ans+1);
	}
}

###两个串问题

解决这类问题的宗旨就是先连接两个字符串，中间用特殊字符分隔，然后对新字符串用后缀数组处理。
####公共子串
两个串最长公共子串问题
[POJ2774] Long Long Message
由于一个串的任意一个子串都可以表示为其一个后缀的前缀，所以求两个串的最长公共子串就是求两个串后缀的最长公共前缀的最大值，这样做的话需要枚举两个串的后缀，时间复杂度为 $O(N^2)$ ，效率低下。

我们考虑把两个子串接在一起，中间用特殊字符隔开，用后缀数组处理这个新的串，易得：
$$ans=Max_{2\leq i\leq n+1}^{2\leq j\leq n+1}LCP(i,j)\quad \text{suffix}\ i \text{ and}\ j \ \text{belong to different string}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=1e5+5;

int sa[MAXN],t1[MAXN],t2[MAXN],c[MAXN];
inline bool isSim(int *na,int o,int la,int len)
{return na[o]==na[la]&&na[o+len]==na[la+len];}
void buildSA(int *na,int n,int m)
{
	int i,j,p,*x=t1,*y=t2;
	memset(c,0,sizeof(c));
	for(i=0;i<n;i++) c[x[i]=na[i]]++;
	for(i=1;i<m;i++) c[i]+=c[i-1];
	for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
	for(j=p=1;p<n;j<<=1,m=p)
	{
		for(i=n-j,p=0;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]-j>=0) y[p++]=sa[i]-j;
		memset(c,0,sizeof(c));
		for(i=0;i<n;i++) c[x[y[i]]]++;
		for(i=1;i<m;i++) c[i]+=c[i-1];
		for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
		swap(x,y);
		p=1,x[sa[0]]=0;
		for(i=1;i<n;i++)
			x[sa[i]]=isSim(y,sa[i],sa[i-1],j)?p-1:p++;
	}
}
int rk[MAXN],ht[MAXN];
void calHt(int *na,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rk[sa[i]]=i;
	for(i=0;i<n;i++)
	{
		if(k) k--;
		j=sa[rk[i]-1];
		while(na[i+k]==na[j+k]) k++;
		ht[rk[i]]=k;
	}
}
char s1[MAXN],s2[MAXN];
int na[MAXN<<<1];
int main()
{
	int i,mid,n;
	scanf("%s%s",s1,s2);
	mid=strlen(s1);n=strlen(s2)+mid+1;
	for(i=0;i<mid;i++) na[i]=s1[i];na[mid]=1;
	for(i=mid+1;i<n;i++) na[i]=s2[n-(mid+1)];na[n]=0;
	buildSA(na,n+1,256);
	calHeight(na,n);
	int ans=0;
	for(i=2;i<=n;i++)
		if((sa[i]<mid&&mid<sa[i-1])||(sa[i-1]<mid&&mid<sa[i]))
			ans=max(ans,ht[i]);
	printf("%d\n",ans);
}

###多个串问题

##参考文献
[1] 罗穗骞. 后缀数组——处理字符串的有力工具[D]. 北京:中国计算机协会, 2009.
[2] 刘汝佳, 陈锋. 算法竞赛从入门到精通——训练指南[M]. 北京:清华大学出版社, 2012. 219-227
[3] CXCXCXC. 用 二分+哈希 求后缀数组[EB/OL]. http://www.cnblogs.com/CXCXCXC/p/5380755.html, 2016-04-11
[3] Menci. 后缀数组学习笔记[EB/OL]. https://oi.men.ci/suffix-array-notes/, 2016-04-12