HDU 1403 Longest Common Substring（后綴數組啊 求最長公共子串 模板題）
來源：程序員人生 發布時間：2015-09-07 08:20:34 閱讀次數：4092次
題目鏈接：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
