题解 P5829 【【模板】失配树】

[几年不更新一次的博客](https://www.luogu.com.cn/blog/RainbowCat/) **前排Orz出题人和扶苏爷。** 完全没听说过border树这个东西。。。。。 但是我们可以发现，border的定义和我们做kmp时所求的fail数组基本一致。 一个显然的结论是，对于A<--fail--B<--fail--C，A与C显然能也形成border。 根据这个传递性，我们就可以在fail数组上倍增，二分最靠右的交汇点编号，让两个点倍增去跳即可，O(nlog^2n)。 回忆树上倍增lca，这里之所以要二分的原因就是没法把两个点提到同一高度（这里相当于以编号作为高度，因此每个点高度都不同）。 模仿树上倍增的套路，按照fail链长度给每个点设置一下高度，树上倍增即可。时间复杂度O(nlogn)，即O(能过)。 要注意的是因为border不能是整个串，所以两个点必须都跳至少一次。 ~~（不知道这个是不是border树）~~ 不过本题并没必要显式的连边建一颗树出来。 ```cpp #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int kmaxlog=25; const int kmaxn=1000000+5; const int ml=21; int fail[kmaxn]; int fa[kmaxn][kmaxlog]; int dis[kmaxn]; char s[kmaxn]; int n,q; void init() { int p=0; for(int i=2;i<=n;++i) { while(p&&s[p+1]!=s[i]) p=fail[p]; if(s[p+1]==s[i])++p; fail[i]=p; dis[i]=dis[p]+1; fa[i][0]=p; } for(int k=1;k<=ml;++k) { for(int i=1;i<=n;++i) fa[i][k]=fa[fa[i][k-1]][k-1]; } } int jmp(int x,int h) { if(dis[x]<=h)return x; for(int i=ml;i>=0;--i) { if(dis[fa[x][i]]>h) x=fa[x][i]; } return fa[x][0]; } int lca(int x,int y) { if(dis[x]<dis[y])swap(x,y); x=jmp(x,dis[y]); for(int i=ml;i>=0;--i) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } int a,b; int main() { scanf("%s%d",&s[1],&q); n=strlen(s+1); init(); while(q--) { scanf("%d%d",&a,&b); printf("%d\n",lca(a,b)); } return 0; } ``` 刚看到题时候傻了以为hash就能搞，还看错了题，日常丢人。