「地区旅行」问题题解

问题分析

我们需要处理多个地区描述字符串，并回答多个查询：对于两个字符串的特定前缀，找到它们的最长公共后缀，且这个后缀必须是一个真实存在的地区描述。

核心思路

使用 AC自动机 + 树链剖分/LCA 的解法：

1. AC自动机：将所有地区描述插入Trie树，构建fail指针
2. 树链剖分：在fail树上进行树链剖分，快速求LCA
3. LCA查询：两个节点在fail树上的LCA对应它们的最长公共后缀

算法详解

1. AC自动机构建

struct ACam {
    int tot, fail[N], ch[N][M], ans[N];
    void insert(char *s, int id) {
        int u = 0, len = strlen(s);
        pre[id].pb(0);  // 记录每个前缀对应的节点
        
        for (int i = 0; i < len; i++) {
            int x = s[i] - 'a';
            if (!ch[u][x])
                ch[u][x] = ++tot, ans[ch[u][x]] = (1ll * ans[u] * 26 % mod + x) % mod;
            u = ch[u][x];
            pre[id].pb(u);  // 记录前缀节点
        }
    }
    
    void build() {
        // 构建fail指针，建立fail树
        for (int i = 0; i < 26; i++)
            if (ch[0][i]) q.push(ch[0][i]);
            
        while (q.size()) {
            int x = q.front(); q.pop();
            addedge(fail[x], x);  // 在fail树中添加边
            
            for (int i = 0; i < 26; i++)
                if (ch[x][i])
                    fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
                else
                    ch[x][i] = ch[fail[x]][i];
        }
    }
} T;

关键点：

• pre[id] 记录字符串每个前缀对应的Trie节点
• ans[u] 存储从根到节点u路径的26进制编码值
• fail指针构成一棵树（fail树）

2. 树链剖分预处理

void dfs1(int x) {
    sz[x] = 1;
    dep[x] = dep[fa[x]] + 1;
    
    for (int i = h[x]; i; i = nxt[i]) {
        fa[to[i]] = x;
        dfs1(to[i]);
        sz[x] += sz[to[i]];
        if (!son[x] || sz[to[i]] > sz[son[x]])
            son[x] = to[i];
    }
}

void dfs2(int x, int tp) {
    top[x] = tp;
    if (!son[x]) return;
    dfs2(son[x], tp);
    
    for (int i = h[x]; i; i = nxt[i])
        if (to[i] != son[x])
            dfs2(to[i], to[i]);
}

在fail树上进行树链剖分，为快速LCA查询做准备。

3. LCA查询

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
        y = fa[top[y]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return x;
}

4. 查询处理

while (m--) {
    int i, j, k, l;
    scanf("%d%d%d%d", &i, &j, &k, &l);
    printf("%d\n", T.ans[lca(pre[i][j], pre[k][l])]);
}

查询解释：

• pre[i][j]：第i个字符串前j个字符对应的Trie节点
• pre[k][l]：第k个字符串前l个字符对应的Trie节点
• 它们在fail树上的LCA对应最长公共后缀节点
• T.ans[lca] 直接给出该后缀的编码值

算法正确性

为什么LCA对应最长公共后缀？

在AC自动机的fail树中：

• 节点u代表某个前缀
• u的祖先代表u的所有后缀
• 两个节点的LCA代表它们的最长公共后缀

为什么这个后缀一定是真实地区？

因为AC自动机中只插入了真实的地区描述，所以LCA节点对应的字符串一定是某个真实地区。

复杂度分析

• AC自动机构建：$O(\text{总长度})$
• 树链剖分：$O(\text{节点数})$
• 每次查询：$O(\log n)$
• 总复杂度：$O(\text{总长度} + m \log n)$

样例验证

样例输入：

2
aabb  
babb
2
1 3 2 3  // s1前3位:aab, s2前3位:bab
1 4 2 4  // s1前4位:aabb, s2前4位:babb

处理过程：

1. 构建AC自动机，插入"aabb"和"babb"
2. 对于查询1：节点aab和bab的LCA对应"b"
3. 对于查询2：节点aabb和babb的LCA对应"b"
4. "b"的编码为1，输出两个1

总结

本题的巧妙之处在于：

1. 问题转化：将最长公共后缀问题转化为fail树上的LCA问题
2. AC自动机应用：利用fail树的性质高效求解
3. 树链剖分优化：加速LCA查询
4. 预处理编码：在插入时直接计算每个节点的编码值

这种"字符串问题 → AC自动机 → 树问题"的转化思路在解决复杂字符串问题时非常有效。