角门网站建设,网站开发合同验收,晋江网友交流区网站,珠宝wordpress主题失配树#xff0c;是一种奇妙的数据结构#xff0c;它利用 KMP、LCA 解决求两前缀的最长公共 Border 的问题。
首先介绍一下什么是 Border#xff0c;我们知道 nxt 数组是前后缀相同的最大长度#xff0c;Border 相当于是 nxt 数组的弱化版#xff0c;只是去掉了“最大”…失配树是一种奇妙的数据结构它利用 KMP、LCA 解决求两前缀的最长公共 Border 的问题。
首先介绍一下什么是 Border我们知道 nxt 数组是前后缀相同的最大长度Border 相当于是 nxt 数组的弱化版只是去掉了“最大”的限制。
我们考虑如何建立一棵失配树fail 树对于每一个长度为 i i i 的前缀我们预处理出它的 nxt然后按照 i i i 指向 nxt[i]即 nxt[i] 是 i i i 的爹。
对于两个前缀的最长 Border我们只需要对于两个区间的 i i i、 j j j 求出它们的 LCA 即可。这里需要注意一个坑如果 i i i 和 j j j 的 LCA 是他们中的一个那么我们要把 LCA 上提一步即返回 f[i][0] 或 f[j][0]返回他们的父亲。 练手板子题
代码如下
#include bits/stdc.h
using namespace std;const int maxn1e65;
char s[maxn];
int f[maxn][25],dep[maxn];int lca(int x,int y)
{if(dep[x]dep[y]) swap(x,y);for(int i20;i0;i--) if(dep[f[x][i]]dep[y]) xf[x][i];if(xy) return f[x][0];for(int i20;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}int main()
{scanf(%s,s1);int lenstrlen(s1);f[0][0]f[1][0]0;dep[0]0;dep[1]1;for(int i1,j0;ilen;i){while(js[i1]!s[j1]) jf[j][0];if(s[i1]s[j1]) j;f[i1][0]j,dep[i1]dep[j]1;}int m;cinm;for(int j1;j20;j) for(int i1;ilen;i) f[i][j]f[f[i][j-1]][j-1];while(m--){int p,q;cinpq;coutlca(p,q)endl;}return 0;
}
