考虑把原字符串先\(kmp\)一遍,求出以\(i\)结尾的前缀的最长\(border\),根据\(border\)的\(border\)还是\(border\)这个定理,我们在寻找前缀\(p\)和前缀\(q\)的最长公共\(border\)时,我们可以考虑运用这个定理,一直往前跳,找到最先一样的\(border\),这就是最长公共\(bordedr\),至于优化,我们可以使用倍增
细节,\(border\)不能是自身,所以在\(p\)跳完\(border\)后即使是为\(q\),也不能直接输出\(q\)。
上代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+50;
char s[N];
ll n,m,fa[N][22],dep[N],p,q;
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
fa[0][0]=fa[1][0]=0,dep[0]=0,dep[1]=1;
for(ll i=2,j=0;i<=n;i++)
{
while(j!=0&&s[j+1]!=s[i]) j=fa[j][0];
if(s[j+1]==s[i]) j++;
fa[i][0]=j,dep[i]=dep[j]+1;
}
for(ll i=1;i<=21;i++)
for(ll j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
scanf("%lld",&m);
while(m--)
{
scanf("%lld %lld",&p,&q);
if(dep[p]<dep[q]) swap(p,q);
for(ll i=21;i>=0;i--) if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
for(ll i=21;i>=0;i--) if(fa[p][i]!=fa[q][i]) p=fa[p][i],q=fa[q][i];
printf("%lld\n",fa[p][0]);
}
return 0;
}
标签:前缀,dep,失配,ll,笔记,学习,fa,border
From: https://www.cnblogs.com/pengchujie/p/17658965.html