hdu1403(后缀数组求lcs模板)

2017年08月18日 10点热度 0人点赞 0条评论

Longest Common Substring

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6706    Accepted Submission(s): 2378


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

banana
cianaic
 


Sample Output

3
 

#include
#include
#include
using namespace std;
const int MAXN=200010;
char s[MAXN];
int sa[MAXN],t1[MAXN],t2[MAXN],c[MAXN];
int Rank[MAXN],height[MAXN];
/*
Rank[i]代表后缀i在sa数组中的下标,height[i]定义为sa[i-1]和sa[i]的最长公共前缀(LCP)长度 
*/ 
void build_sa(int n,int m)
{
	//构造字符串s的后缀数组,每个字符值必须为0~m-1
    int i,p,*x=t1,*y=t2; 
    for(i=0;i=0;i--)sa[--c[x[i]]]=i;
    for(int j=1;j<=n;j<<=1)
    {
        p=0;
        for(i=n-j;i=j)y[p++]=sa[i]-j;
        for(i=0;i=0;i--)sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i=n)break;
        m=p;
    }
}
void getHeight(int n)
{
//一共有n个字符
    int i,j,k=0;
    for(i=0;i<=n;i++)Rank[sa[i]]=i;
    for(i=0;ians&&(sa[i-1]len||sa[i-1]>len&&sa[i]
未经允许不得转载!hdu1403(后缀数组求lcs模板)

update

纸上得来终觉浅, 绝知此事须躬行。