题目描述

通常两个押韵的单词末尾字符序列相同。我们利用这一特性定义了"反押韵"的概念。反押韵是指一对单词具有相似的开头。反押韵的程度定义为最长字符串 $S$ 的长度，使得两个字符串都以 $S$ 开头。

例如：

• arboreal 和 arcturus 是一个程度为 $2$ 的反押韵对
• chalkboard 和 overboard 是一个程度为 $0$ 的反押韵对

给定一个单词列表和若干查询 $(i,j)$，要求输出第 $i$ 个和第 $j$ 个单词的反押韵程度。

输入格式

• 第一行：测试用例数 $T$ ($T\le 35$)
• 每个测试用例：
  • 第一行：字符串数量 $N$ ($1\le N\le 10^5$)
  • 接下来 $N$ 行：每个字符串（仅小写字母，长度 $L\le 10^4$）
  • 下一行：查询数 $Q$ ($1\le Q\le 10^6$)
  • 接下来 $Q$ 行：每行两个整数 $i$ 和 $j$ ($1\le i,j\le N$)

重要约束：$N\times L\le 10^6$

输出格式

对于每个测试用例：

• 第一行：Case X:（$X$ 为用例编号）
• 接下来 $Q$ 行：每个查询的答案

题目分析

问题本质

我们需要高效地解决多个查询：对于任意两个字符串，找出它们的最长公共前缀（$\text{LCP}$）的长度。

约束条件分析

• $N$ 最多 $10^5$，$Q$ 最多 $10^6$，$L$ 最多 $10^4$
• 关键约束：$N\times L\le 10^6$（总字符数有限）
• 如果对每个查询都直接比较两个字符串，最坏情况时间复杂度为 $O(Q\times L)$，可能达到 $10^{10}$ 次操作，显然不可行

核心挑战

如何在预处理后，用接近 $O(1)$ 的时间回答每个查询？

解题思路

关键观察

两个字符串的最长公共前缀长度等于它们在 $\text{Trie}$ 树 中对应节点的最近公共祖先（$\text{LCA}$）的深度。

算法设计

1. 构建 $\text{Trie}$ 树

   • 将所有字符串插入到 Trie 中
   • 每个节点记录深度和父节点信息
   • 记录每个字符串在 Trie 中的结束节点

2. $\text{LCA}$ 预处理

   • 使用 $\text{DFS}$ 生成 $\text{Trie}$ 的欧拉序
   • 记录每个节点的首次出现位置
   • 使用 $\text{RMQ}$（范围最小值查询）技术预处理欧拉序，支持 $O(1)$ 的 $\text{LCA}$ 查询

3. 查询处理

   • 对于查询 $(i,j)$，找到两个字符串在 $\text{Trie}$ 中的结束节点
   • 查询这两个节点的 $\text{LCA}$
   • $\text{LCA}$ 的深度即为最长公共前缀长度

复杂度分析

• 构建 Trie：$O(\text{总字符数})=O(10^6)$
• DFS 欧拉序：$O(\text{Trie 节点数})$
• RMQ 预处理：$O(n\log n)$，其中 $n$ 为欧拉序列长度
• 每个查询：$O(1)$

总复杂度：$O(\text{总字符数}+Q)$，在约束范围内可行。

算法细节

$\text{Trie}$ 树结构

struct TrieNode {
    int depth;        // 节点深度（根节点深度为0）
    int parent;       // 父节点索引
    int children[26]; // 子节点指针
};

$\text{LCA}$ 与 $\text{RMQ}$

• 欧拉序：$\text{DFS}$ 遍历 $\text{Trie}$ 时记录访问的节点序列
• 首次出现位置：记录每个节点在欧拉序中第一次出现的位置
• $\text{RMQ}$：在欧拉序上，两个节点的 $\text{LCA}$ 就是它们首次出现位置之间深度最小的节点

查询过程

对于字符串 $i$ 和 $j$：

1. 获取它们在 $\text{Trie}$ 中的结束节点 $u$ 和 $v$
2. 查询 $u$ 和 $v$ 的 $\text{LCA}$ 节点 $l$
3. 输出 $depth[l]$ 作为答案

代码实现

// Anti-Rhyme Pairs
// UVa ID: 12338
// Verdict: Accepted
// Submission Date: 2025-11-08
// UVa Run Time: 0.160s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN = 100005;
const int MAXL = 10005;
const int MAX_NODES = 1000005; // 因为 N * L <= 1e6

struct TrieNode {
    int depth;
    int parent;
    int children[26];
    TrieNode() : depth(0), parent(-1) {
        memset(children, -1, sizeof(children));
    }
};

vector<TrieNode> trie;
int wordEnd[MAXN]; // 记录每个单词在 Trie 中的结束节点

int addNode(int parent) {
    int idx = trie.size();
    trie.emplace_back();
    trie[idx].parent = parent;
    trie[idx].depth = (parent == -1) ? 0 : trie[parent].depth + 1;
    return idx;
}

void insert(const string& s, int wordIndex) {
    int node = 0; // root
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[node].children[c] == -1) {
            int newNode = addNode(node);
            trie[node].children[c] = newNode;
        }
        node = trie[node].children[c];
    }
    wordEnd[wordIndex] = node;
}

// LCA 相关
vector<int> euler;
int firstOccurrence[MAX_NODES];
int depth[MAX_NODES];
int eulerIndex;

void dfs(int u) {
    firstOccurrence[u] = eulerIndex;
    euler.push_back(u);
    eulerIndex++;
    for (int i = 0; i < 26; i++) {
        int v = trie[u].children[i];
        if (v != -1) {
            depth[v] = depth[u] + 1;
            dfs(v);
            euler.push_back(u);
            eulerIndex++;
        }
    }
}

vector<vector<int>> st;
vector<int> logTable;

void buildRMQ() {
    int n = euler.size();
    logTable.resize(n + 1);
    logTable[1] = 0;
    for (int i = 2; i <= n; i++) {
        logTable[i] = logTable[i / 2] + 1;
    }
    int k = logTable[n] + 1;
    st.assign(n, vector<int>(k));
    for (int i = 0; i < n; i++) {
        st[i][0] = euler[i];
    }
    for (int j = 1; j < k; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            int left = st[i][j - 1];
            int right = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (depth[left] < depth[right]) ? left : right;
        }
    }
}

int queryLCA(int u, int v) {
    int l = firstOccurrence[u];
    int r = firstOccurrence[v];
    if (l > r) swap(l, r);
    int j = logTable[r - l + 1];
    int leftNode = st[l][j];
    int rightNode = st[r - (1 << j) + 1][j];
    return (depth[leftNode] < depth[rightNode]) ? leftNode : rightNode;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int caseNum = 1; caseNum <= T; caseNum++) {
        int n;
        cin >> n;
        trie.clear();
        addNode(-1); // root

        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            insert(s, i);
        }

        // 准备 LCA
        euler.clear();
        eulerIndex = 0;
        depth[0] = 0;
        dfs(0);
        buildRMQ();

        int q;
        cin >> q;
        cout << "Case " << caseNum << ":\n";
        while (q--) {
            int i, j;
            cin >> i >> j;
            i--; j--;
            int u = wordEnd[i];
            int v = wordEnd[j];
            int lca = queryLCA(u, v);
            cout << trie[lca].depth << "\n";
        }
    }

    return 0;
}

总结

本题通过将最长公共前缀问题转化为 $\text{Trie}$ 树上的 $\text{LCA}$ 问题，利用欧拉序和 $\text{RMQ}$ 技术实现了 $O(1)$ 的查询响应。这种"问题转化+数据结构优化"的思路在字符串处理问题中非常常见，值得学习和掌握。

关键技巧：

• $\text{Trie}$ 树用于处理前缀相关问题
• 欧拉序 + $\text{RMQ}$ 用于高效 $\text{LCA}$ 查询
• 充分利用题目约束条件进行优化