题目链接:https://cn.vjudge.net/contest/283743#problem/J
题目大意:给你两个字符串,问你两个字符串的最长的公共子串。
具体思路:把两个字符串合在一起,然后求后缀数组,按照排名之后的字符串,如果两个相邻的字符串的sa[i]和sa[i-1]分别属于两个字符串,那么这个就是题目允许的值之一,然后再从这些值里面找一个最大的输出就可以了。
AC代码:
#include<iostream>
#include<stack>
#include<cstring>
#include<iomanip>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 5e5+;
int cntA[maxn], cntB[maxn], sa[maxn], tsa[maxn], A[maxn], B[maxn], height[maxn];
int Rank[maxn];
char ch[maxn];
char str1[maxn];
int sto[maxn];
ll n;
//sa[i]代表第i小的后缀位置,Rank[i]代表第i位置的后缀,排名第几小
// height[i]代表排名第i个字符串和第i-1个字符串的相同前缀有多少个
void cal()
{
for(int i = ; i < ; i++)
cntA[i] = ;
for(int i = ; i <= n; i++)
{
cntA[ch[i-]]++;
}
for(int i = ; i < ; i++)
cntA[i] += cntA[i-];
for(int i = n; i; i--)
sa[cntA[ch[i-]]--] = i;
Rank[sa[]] = ;
for(int i = ; i <= n; i++)
{
Rank[sa[i]] = Rank[sa[i-]];
if(ch[sa[i]-] != ch[sa[i-]-])
Rank[sa[i]]++;
}
for(int l = ; Rank[sa[n]] < n; l <<= )
{
memset(cntA, , sizeof(cntA));
memset(cntB, , sizeof(cntB));
for(int i = ; i <= n; i++)
{
cntA[A[i] = Rank[i]]++;
cntB[B[i] = (i+l <= n)?Rank[i+l]:]++;
}
for(int i = ; i <= n; i++)
cntB[i] += cntB[i-];
for(int i = n; i; i--)
tsa[cntB[B[i]]--] = i;
for(int i = ; i <= n; i++)
cntA[i] += cntA[i-];
for(int i = n; i; i--)
sa[cntA[A[tsa[i]]]--] = tsa[i];
Rank[sa[]]=;
for(int i = ; i <= n; i++)
{
Rank[sa[i]] = Rank[sa[i-]];
if(A[sa[i]] != A[sa[i-]] || B[sa[i]] != B[sa[i-]])
Rank[sa[i]]++;
}
}
for(int i = , j = ; i <= n; i++)
{
if(j)
j--;
while(ch[i+j-] == ch[sa[Rank[i]-] + j - ])
j++;
height[Rank[i]] = j;
}
}
int main()
{
scanf("%s",str1);
int len1=strlen(str1);
for(int i=; i<len1; i++)
{
ch[i]=str1[i];
}
scanf("%s",str1);
int len2=strlen(str1);
for(int i=len1; i<len1+len2; i++)
{
ch[i]=str1[i-len1];
}
n=len1+len2;
cal();
int maxx=;
for(int i=; i<=len1+len2; i++)
{
if(height[i]>maxx)
{
if(sa[i]>=&&sa[i]<=len1&&sa[i-]>=(+len1)&&sa[i-]<=len1+len2)
maxx=height[i];
if(sa[i-]>=&&sa[i-]<=len1&&sa[i]>=(+len1)&&sa[i]<=len1+len2)
maxx=height[i];
}
}
printf("%d\n",maxx);
return ;
}