HDU 1403 Longest Common Substring（后缀数组啊 求最长公共子串 模板题）

#include <cstdio> #include <cstring> const int N = 100017*2; int wa[N], wb[N], wv[N], ws[N]; int rank[N]; //名次数组 int height[N]; //排名相邻的两个后缀的最长公共前缀 char str[N]; int s[N], sa[N]; //sa为后缀数组,n个后缀从小到大进行排序以后把排好序的后缀的开头位置 int Max(int a, int b) { return a > b ? a:b; } int Min(int a, int b) { return a < b ? a:b; } int cmp(int *r, int a, int b, int l) { return r[a]==r[b] && r[a+l]==r[b+l]; } //get_sa函数的参数n代表字符串中字符的个数，这里的n里面是包括人为在字符串末尾添加的那个0的 //get_sa函数的参数m代表字符串中字符的取值范围，是基数排序的1个参数， //如果原序列都是字母可以直接取128， //如果原序列本身都是整数的话，则m可以取比最大的整数大1的值。 void get_sa(int *r, int *sa, int n, int m) //倍增算法 { int i,j,p,*x=wa,*y=wb,*t; for(i=0; i<m; i++) ws[i]=0; for(i=0; i<n; i++) ws[x[i]=r[i]]++; for(i=1; i<m; i++) ws[i]+=ws[i⑴]; for(i=n⑴; i>=0; i--) sa[--ws[x[i]]]=i; //对长度为1的字符串排序 for(p=1,j=1; p<n; j*=2,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; //第2关键字排序结果 for(i=0; i<n; i++) wv[i]=x[y[i]]; for(i=0; i<m; i++) ws[i]=0; for(i=0; i<n; i++) ws[wv[i]]++; for(i=1; i<m; i++) ws[i]+=ws[i⑴]; for(i=n⑴; i>=0; i--) sa[--ws[wv[i]]]=y[i]; //第1关键字排序 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i⑴],sa[i],j)?p⑴:p++; //更新rank数组 } return; } void get_height(int *r, int *sa, int n) //求height数组 { int i, j, k=0; for(i=1; i<=n; i++) rank[sa[i]]=i; for(i=0; i<n; height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]⑴]; r[i+k]==r[j+k]; k++); return; } int main() { while(~scanf("%s",str)) { int len = strlen(str); str[len] = '~'; scanf("%s",str+len+1); int LEN = strlen(str); for(int i = 0; i < LEN; i++) { s[i] = str[i]-'a'+1; } s[LEN] = 0; get_sa(s,sa,LEN,270); get_height(s,sa,LEN); int ans = 0; for(int i = 2; i < LEN; i++) { if(height[i] > ans) { if((sa[i⑴]<len&&sa[i]>len) || (sa[i⑴]>len&&sa[i]<len)) ans = height[i]; } } printf("%d ",ans); } return 0; }