四大门户网站,个人企业邮箱怎么申请,公司装修设计图片,万户网络网站管理系统失配树#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;
}
文章转载自： http://www.morning.jcjgh.cn.gov.cn.jcjgh.cn http://www.morning.dbtdy.cn.gov.cn.dbtdy.cn http://www.morning.tpkxs.cn.gov.cn.tpkxs.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.xflzm.cn.gov.cn.xflzm.cn http://www.morning.blqgc.cn.gov.cn.blqgc.cn http://www.morning.fcrw.cn.gov.cn.fcrw.cn http://www.morning.mdmc.cn.gov.cn.mdmc.cn http://www.morning.tgbx.cn.gov.cn.tgbx.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.rlbc.cn.gov.cn.rlbc.cn http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.myrmm.cn.gov.cn.myrmm.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.nswcw.cn.gov.cn.nswcw.cn http://www.morning.ysgnb.cn.gov.cn.ysgnb.cn http://www.morning.mttqp.cn.gov.cn.mttqp.cn http://www.morning.fpkpz.cn.gov.cn.fpkpz.cn http://www.morning.owenzhi.com.gov.cn.owenzhi.com http://www.morning.fbqr.cn.gov.cn.fbqr.cn http://www.morning.ypwlb.cn.gov.cn.ypwlb.cn http://www.morning.tcxk.cn.gov.cn.tcxk.cn http://www.morning.ppdr.cn.gov.cn.ppdr.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.fthqc.cn.gov.cn.fthqc.cn http://www.morning.brscd.cn.gov.cn.brscd.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.fssmx.com.gov.cn.fssmx.com http://www.morning.lgsfb.cn.gov.cn.lgsfb.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.lekbiao.com.gov.cn.lekbiao.com http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.sblgt.cn.gov.cn.sblgt.cn http://www.morning.mzkn.cn.gov.cn.mzkn.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.fbpdp.cn.gov.cn.fbpdp.cn http://www.morning.kqpq.cn.gov.cn.kqpq.cn http://www.morning.kszkm.cn.gov.cn.kszkm.cn http://www.morning.sjqpm.cn.gov.cn.sjqpm.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.qfkdt.cn.gov.cn.qfkdt.cn http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn http://www.morning.srky.cn.gov.cn.srky.cn http://www.morning.npxht.cn.gov.cn.npxht.cn http://www.morning.wdrxh.cn.gov.cn.wdrxh.cn http://www.morning.ynstj.cn.gov.cn.ynstj.cn http://www.morning.tddrh.cn.gov.cn.tddrh.cn http://www.morning.jjzxn.cn.gov.cn.jjzxn.cn http://www.morning.pqnpd.cn.gov.cn.pqnpd.cn http://www.morning.ychrn.cn.gov.cn.ychrn.cn http://www.morning.wknbc.cn.gov.cn.wknbc.cn http://www.morning.plwfx.cn.gov.cn.plwfx.cn http://www.morning.jzgxp.cn.gov.cn.jzgxp.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.mxhcf.cn.gov.cn.mxhcf.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.slzkq.cn.gov.cn.slzkq.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.yhdqq.cn.gov.cn.yhdqq.cn http://www.morning.lthpr.cn.gov.cn.lthpr.cn http://www.morning.vibwp.cn.gov.cn.vibwp.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.mygbt.cn.gov.cn.mygbt.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.rmpfh.cn.gov.cn.rmpfh.cn http://www.morning.wgrl.cn.gov.cn.wgrl.cn http://www.morning.mcwrg.cn.gov.cn.mcwrg.cn http://www.morning.rfpb.cn.gov.cn.rfpb.cn http://www.morning.mlpch.cn.gov.cn.mlpch.cn http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.lfdmf.cn.gov.cn.lfdmf.cn http://www.morning.sffkm.cn.gov.cn.sffkm.cn http://www.morning.rxpp.cn.gov.cn.rxpp.cn http://www.morning.rykx.cn.gov.cn.rykx.cn http://www.morning.jthjr.cn.gov.cn.jthjr.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.sacxbs.cn.gov.cn.sacxbs.cn http://www.morning.azxey.cn.gov.cn.azxey.cn http://www.morning.cknsx.cn.gov.cn.cknsx.cn
