JZOJ 4348 打击目标

首先讲题解做法，也是我第一个想到的做法。

对 m1…N 建 AC 自动机，将询问串放在其上匹配，最后走到的状态和其 Fail 树上的全部祖先便是对这个询问串有贡献的。
然后还有一个树上路径的限制，考虑在 Fail 树上用主席树按照树剖的 DFS 序维护每个状态到根路径上的贡献。

然后讲一个假在线做法。
注意到询问串并没有加密，考虑对询问串建广义 SAM，把 m1…N 放在其上匹配，最后走到的状态和其 Parent Tree 上的子树内的状态便是每个模式串贡献到的询问串。
同样建到根路径上的主席树，但是要对询问串的每一个前缀统计贡献。

然后讲一个小常数简单做法，也就是我写的做法。
考虑枚举询问串中匹配的起始位置，枚举匹配长度，在原树上建可持久化 Trie 维护每个结点到根路径上的字符串，通过差分得到一段树上路径的 Trie，如此匹配。

前两个做法都是 O(∑|w|log2n) 的，最后一个是 O(max|mi|∑|w|) 的。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int M = 1e6;
const int L = 10;
int n,m,online,q;
char a[N + 5][L + 5],s[N + 5];
int len[N + 5],ans;
namespace TRIE
{
    struct node
    {
        int ch[26];
        int sum,ed;
    } trie[M + 5];    
    void insert(char *s,int len,int &rt)
    {
        static int tot = 0;
        trie[++tot] = trie[rt],++trie[rt = tot].sum;
        int p = rt;
        for(register int i = 1;i <= len;++i)
            trie[++tot] = trie[trie[p].ch[s[i] - 'a']],++trie[p = trie[p].ch[s[i] - 'a'] = tot].sum;
        ++trie[p].ed;
    }
    int query(char *s,int len,int p,int q,int x,int y)
    {
        if(!(trie[p].sum + trie[q].sum - trie[x].sum - trie[y].sum))
            return 0;
        int ret = 0;
        for(register int i = 1;i <= len;++i)
        {
            p = trie[p].ch[s[i] - 'a'],q = trie[q].ch[s[i] - 'a'],x = trie[x].ch[s[i] - 'a'],y = trie[y].ch[s[i] - 'a'];
            if(!(trie[p].sum + trie[q].sum - trie[x].sum - trie[y].sum))
                break;
            if(trie[p].ed + trie[q].ed - trie[x].ed - trie[y].ed)
                ret = max(ret,i);
        }
        return ret;
    }
}
namespace HLD
{
    int to[N + 5],pre[N + 5],first[N + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5];
    int rt[N + 5];
    int q[N + 5],head,tail;
    void bfs()
    {
        dep[q[++tail] = 1] = 1;
        for(register int p;head < tail;)
        {
            sz[p = q[++head]] = 1,TRIE::insert(a[p],len[p],rt[p] = rt[fa[p]]);
            for(register int i = first[p];i;i = pre[i])
                dep[to[i]] = dep[p] + 1,q[++tail] = to[i];
        }
        for(register int i = n;i > 1;--i)
        {
            sz[fa[q[i]]] += sz[q[i]];
            if(!son[fa[q[i]]] || sz[q[i]] > sz[fa[q[i]]])
                son[fa[q[i]]] = q[i];
        }
        for(register int i = 1;i <= n;++i)
            top[q[i]] = q[i] == son[fa[q[i]]] ? top[fa[q[i]]] : q[i];
    }
    int getlca(int x,int y)
    {
        while(top[x] ^ top[y])
            dep[top[x]] > dep[top[y]] ? (x = fa[top[x]]) : (y = fa[top[y]]);
        return dep[x] < dep[y] ? x : y;
    }
}
int main()
{
    scanf("%d%d",&n,&online);
    for(register int i = 1;i <= n;++i)
        scanf("%s",a[i] + 1),len[i] = strlen(a[i] + 1);
    for(register int i = 2;i <= n;++i)
        scanf("%d",HLD::fa + i),HLD::add(HLD::fa[i],i);
    HLD::bfs();
    scanf("%d",&q);
    for(int x,y,lca;q;--q)
    {
        scanf("%d%d%s",&x,&y,s + 1),online && (x ^= ans,y ^= ans),ans = 0,m = strlen(s + 1);
        lca = HLD::getlca(x,y);
        for(register int i = 1;i <= m;++i)
            ans = max(ans,TRIE::query(s + i - 1,min(L,m - i + 1),HLD::rt[x],HLD::rt[y],HLD::rt[lca],HLD::rt[HLD::fa[lca]]));
        printf("%d\n",ans);
    }
}