1、基本定义。
子串：字符串S的子串r[i...j]。
后缀：以i开始的后缀表示为Suffix(i)。
大小比较：按字典序。
后缀数组：SA是一个一维数组。将S的后缀从小到大排序后，后缀的开头位置顺次放入SA。(SA[i]=j：排在第i个的是Suffix(j))
名词数组：Rank[i]是Suffix(i)在后缀中从小到大排列的名次。(Rank[i]=j：Suffix(i)排在第j个)
后缀数组和名次数组为互逆运算：设Rank[i]=j，则SA[j]=i。
2、倍增算法。
目的：设字符串长度为n，在O(nlog2n)求出SA数组和Rank数组。
1 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; 2 inline bool cmp(int *r,int a,int b,int len) 3 { 4 return r[a]==r[b]&&r[a+len]==r[b+len]; 5 } 6 void SA(char *r,int *sa,int n,int m) 7 { 8 //r为字符串数组，sa为后缀数组，n=strlen(s)+1，m为max(r[i])+1。 9 int i,j,p,*x=wa,*y=wb,*t;10 11 //对长度为1的字符串基数排序。12 for(i=0;i =0;i--)19 sa[--ws[x[i]]]=i;//小于等于r[i]共有ws[x[i]]个，因此r[i]排在第ws[x[i]]个。20 21 for(j=p=1;p <<=1,m=p)//p是第二关键字为0的个数，j是当前比较的字符串长度。22 {23 //对第二关键字基数排序。24 //y[s]=t表示排在第s个的起点在t，即y[s]对第二关键字排序，但y[s]的值指向第一关键字的位置。25 for(p=0,i=n-j;i =j)//如果排在第i个的字符串起点在sa[i]，满足sa[i]>=当前字符串长度j。30 y[p++]=sa[i]-j;//对于sa[i]-j为起点的第二关键字排在前面。31 }32 33 //对第一关键字基数排序。34 for(i=0;i =0;i--)//wv[i]是排在第i个第二关键字对应的第一关键字。41 sa[--ws[wv[i]]]=y[i];//y[i]就是第一关键字的位置。42 for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i
3、后缀数组的应用。
height数组：height[i]=Suffix(sa[i-1])和Suffix(sa[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀。
h数组：h[i]=height[rank[i]]=Suffix(i)和在它前一名的后缀的最长公共前缀。
h数组的性质：h[i]>=h[i-1]-1。
证明：设Suffix(k)是排在Suffix(i-1)前一名的后缀，则它们的最长公共前缀就是h[i-1]。那么Suffix(k+1)将排在Suffix(i)的前面。
a、若Suffix(k)与Suffix(i-1)的最长公共前缀<=1，即h[i-1]<=1，h[i]>=0显然成立。
b、若Suffix(k)与Suffix(i-1)的最长公共前缀>=2，Suffix(k)与Suffix(i-1)同时去掉首字符得到Suffix(k+1)与Suffix(i)，则Suffix(k+1)排在Suffix(i)的前面，且Suffix(k+1)与Suffix(i)的最长公共前缀=h[i-1]-1。设Suffix(t)是排在Suffix(i)前一名的后缀，则它们的最长公共前缀就是h[i]，那么Suffix(t)=Suffix(k+1)或者Suffix(t)排在Suffix(k+1)前面，则h[i]>=h[i-1]-1。
1 int rank[MAXN],height[MAXN]; 2 void Height(int *r,int *sa,int n) 3 { 4 int i,j,k; 5 for(i=1;i<=n;i++) 6 rank[sa[i]]=i; 7 for(i=k=0;i 0，从k-1开始找最长公共前缀。10 return;11 }
1、不可重叠最长重复子串：
2、可重叠的k 次最长重复子串：
3、不相同的子串的个数：
4、最长回文子串：
5、重复次数最多的连续重复子串：、
6、最长公共子串：
7、长度不小于k 的公共子串的个数：
8、不小于k 个字符串中的最长子串：
9、每个字符串至少出现两次且不重叠的最长子串：
其他：