题目链接：
HDU：?pid=1403
POJ: Long Long Message
Problem Description
Given two strings, you have to tell the length of the Longest Common Substring of them.For example:str1 = bananastr2 = cianaicSo 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
bananacianaic
Sample Output
3
题意：
求两个字符串的最长公共子串长度！
代码如下：
#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代表字符串中字符的取值范围，，是基数排序的一个参数，//如果原序列都是字母可以直接取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-1];for(i=n-1; 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; //第二关键字排序结果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-1];for(i=n-1; i>=0; i–) sa[–ws[wv[i]]]=y[i]; //第一关键字排序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-1],sa[i],j)?p-1: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]-1]; 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+1,270);get_height(s,sa,LEN);int ans = 0;for(int i = 2; i < LEN; i++){if(height[i] > ans){if((sa[i-1]<len&&sa[i]>len) || (sa[i-1]>len&&sa[i]<len))ans = height[i];}}printf("%d\n",ans);}return 0;}
正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。
