Longest Common Substring |
| Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 37 Accepted Submission(s): 28 |
|
Problem Description
Given two strings, you have to tell the length of the Longest Common Substring of them.
For example: 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 |
|
Sample Output
3 |
|
Author
Ignatius.L
|
/*----------------------------------------------
File: F:\ACM源代码\数据结构--后缀数组\Longest_Common_Substring.cpp
Date: 2017/5/30 16:55:36
Author: LyuCheng
----------------------------------------------*/
/*
题意：最长公共子序列 思路：问题很多，DP基本不用考虑，因为时间复杂度空间复杂度都不允许，NlogN的算法也不行，最坏的情况
转化成LIS的数组是1e10空间复杂的不允许，所以只能利用后缀数组的性质，将两个连接，然后前后两个
前缀在两个不同的字符串中的时候，更新height的值，因为后缀加前缀，刚好是公共子序列
*/
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
char s1[MAXN],s2[MAXN];
/****************************************后缀数组模板****************************************/
const int maxn=+;
struct SuffixArray
{
char s[maxn];
int sa[maxn],rank[maxn],height[maxn];
int t1[maxn],t2[maxn],c[maxn],n;
int dmin[maxn][];
void build_sa(int m)
{
int i,*x=t1,*y=t2;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[i]=s[i]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(int k=;k<=n;k<<=)
{
int p=;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[y[i]]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[y[i]]]] = y[i];
swap(x,y);
p=,x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]= y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]? p-:p++;
if(p>=n) break;
m=p;
}
}
void build_height()//n不能等于1,否则出BUG
{
int i,j,k=;
for(i=;i<n;i++)rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k)k--;
j=sa[rank[i]-];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
void initMin()
{
for(int i=;i<=n;i++) dmin[i][]=height[i];
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<=n;i++)
dmin[i][j]=min(dmin[i][j-] , dmin[i+(<<(j-))][j-]);
}
int RMQ(int L,int R)//取得范围最小值
{
int k=;
while((<<(k+))<=R-L+)k++;
return min(dmin[L][k] , dmin[R-(<<k)+][k]);
}
int LCP(int i,int j)//求后缀i和j的LCP最长公共前缀
{
int L=rank[i],R=rank[j];
if(L>R) swap(L,R);
L++;//注意这里
return RMQ(L,R);
}
}sa;
/****************************************后缀数组模板****************************************/ int main(){
// freopen("in.txt","r",stdin);
while(scanf("%s%s",s1,s2)!=EOF){
int n=strlen(s1);
int m=strlen(s2);
for(int i=;i<n;i++){
sa.s[i]=s1[i];
}
sa.s[n]='$';
for(int i=n;i<n+m;i++){
sa.s[i]=s2[i-n];
}
sa.n=m+n+;
sa.build_sa(MAXN);
sa.build_height();
int maxLCS=-;
for(int i=;i<m+n+;i++){
if(i==){
maxLCS=max(maxLCS,sa.height[i]);
}else{
if((sa.sa[i]-n)*(sa.sa[i-]-n)<)//保证两后缀是来自不同的字符串的
maxLCS=max(maxLCS,sa.height[i]);
}
}
printf("%d\n",maxLCS);
}
return ;
}