HDU 1403 Longest Common Substring（后綴數(shù)組啊 求最長(zhǎng)公共子串 模板題）
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-09-07 08:20:34 閱讀次數(shù)：4095次
題目鏈接：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
題意：
求兩個(gè)字符串的最長(zhǎng)公共子串長(zhǎng)度！
代碼以下：
#include <cstdio>
#include <cstring>
const int N = 100017*2;
int wa[N], wb[N], wv[N], ws[N];
int rank[N]; //名次數(shù)組
int height[N]; //排名相鄰的兩個(gè)后綴的最長(zhǎng)公共前綴
char str[N];
int s[N], sa[N]; //sa為后綴數(shù)組,n個(gè)后綴從小到大進(jìn)行排序以后把排好序的后綴的開(kāi)頭位置
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函數(shù)的參數(shù)n代表字符串中字符的個(gè)數(shù)，這里的n里面是包括人為在字符串末尾添加的那個(gè)0的
//get_sa函數(shù)的參數(shù)m代表字符串中字符的取值范圍，是基數(shù)排序的1個(gè)參數(shù)，
//如果原序列都是字母可以直接取128，
//如果原序列本身都是整數(shù)的話，則m可以取比最大的整數(shù)大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; //對(duì)長(zhǎng)度為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關(guān)鍵字排序結(jié)果
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關(guān)鍵字排序
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數(shù)組
}
return;
}
void get_height(int *r, int *sa, int n) //求height數(shù)組
{
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;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
