失配树

1.什么是失配树

失配树又称$fail$树，和一个出生至极神奇美丽的算法：$KMP$息息相关

在$KMP$中，我们在构建数组时会不断地失配又不断地相配，而数组中存储的就是该前缀的失配点，我们就会以这个建树

例如对于字符串$ABCABA$，它的$nxt$数组建出来就是$nxt=\{0,0,0,1,2,1\}$，建出的失配树就是这个亚子的

---

2.如何构建失配树

相信聪明的小朋友看了上面那副图已经知道怎么建图了，就是将$nxt_i$连向$i$，这里就直接给出代码了

rode[n+1].push_back( 1 );
for( int i=2,j=0;i<=n;i++ )
{
    while( j && s[i] != s[j+1] ) j=nxt[j];
    if( s[i] == s[j+1] ) j++;
    nxt[i]=j;
    rode[( j ? j : n+1 )].push_back( i );
}

---

3.失配树可以干什么

正如这道题的操作一样，失配树支持我们查询两个前缀的最长公共$border$

我们上树看一下，以任意一点向上行走到根的这一条路径其实就是它的所有$border$从长到短的排列起来

所以对于两点的最长公共$border$，我们不难想到就是求他们两点的失配树上的$lca$即可

注意：如果使用树链剖分求$lca$的话，不能以0为根节点可以把0全部变为n+1最后输出时判断

for( int i=1, p, q;i<=m;i++ )
{
    cin>>p>>q;
    int ans=lca( nxt[p],nxt[q] ); 
    cout<<( ans == n+1 ? 0 : ans )<<"\n";
}