题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1403
Problem Description
Given two strings, you have to tell the length of the Longest Common Substring of them.
For example:
str1 = banana
str2 = cianaic
So the Longest Common Substring is "ana", and the length is 3.
Input
The input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case.
Process to the end of file.
Output
For each test case, you have to tell the length of the Longest Common Substring of them.
Sample Input
Sample Output
题意：
求两个字符串的最长公共子串长度！
代码以下：
#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;
}