题目描述

给定两个单词 $x$ 和 $y$ ，以及一个有限的单词序列 {w1,w2,…,wk}\{w_1, w_2, \ldots, w_k\}{w1​,w2​,…,wk​} 。我们可以在 $x$ 或 $y$ 的右侧追加序列中的单词，每次追加算一次操作。问是否能够通过若干次操作，使得 $x$ 和 $y$ 最终变成完全相同的单词？如果可以，求出最少操作次数；如果不可能，输出 $-1$。

样例分析

样例输入：

2
abba
ab
4
baaabad
aa
badccaa
cc
a
ab
4
bb
ab
ba
aa

样例输出：

5
-1

第一个样例中，初始单词 $x=\text{"abba"}$ ， $y=\text{"ab"}$ 。通过如下操作可以得到相同字符串：

• 向 $x$ 追加 $\text{"aa"}$ 和 $\text{"badccaa"}$ ，得到 $\text{"abbaaabadccaa"}$
• 向 $y$ 追加 $\text{"baaabad"}$ 、 $\text{"cc"}$ 和 $\text{"aa"}$ ，得到 $\text{"abbaaabadccaa"}$

共 $5$ 次操作。

第二个样例中，初始单词 $x=\text{"a"}$ ， $y=\text{"ab"}$ ，虽然互为前缀，但无法通过给定单词序列调整成功，输出 $-1$。

题目分析

关键观察

1. 前缀关系是必要条件
   如果 $x$ 和 $y$ 能够通过追加单词变成相同的字符串 $Z$ ，那么 $Z$ 必然同时以 $x$ 和 $y$ 为前缀。因此，$x$ 和 $y$ 中较短的那个必须是较长那个的前缀。否则直接输出 $-1$。

2. 问题转化
   假设 $x$ 较短， $y$ 较长，且 $y$ 以 $x$ 为前缀。设它们的共同前缀长度为 $l$ ，则：

   • $x$ 已经完全匹配
   • $y$ 还剩余 $y[l:]$ 需要匹配

   但仔细思考会发现，实际情况比这复杂：当向 $x$ 追加单词时，$x$ 变长，可能会超过 $y$ 的当前长度；同理，向 $y$ 追加单词时，$y$ 变长，也可能会超过 $x$ 的当前长度。因此，不能简单地认为只有一方有剩余。

3. 进一步转化
   考虑任意时刻两个字符串的状态。由于它们始终互为前缀（这是操作过程保持的性质），我们可以用较长字符串减去共同前缀后的剩余部分来表示当前状态。例如：

   • 初始状态：$x=\text{"abba"}$ ， $y=\text{"ab"}$ ，共同前缀 $\text{"ab"}$ ，剩余部分 $\text{"ba"}$（来自 $x$）
   • 向 $x$ 追加 $\text{"aa"}$ 后：$x=\text{"abbaaa"}$ ， $y=\text{"ab"}$ ，共同前缀 $\text{"ab"}$ ，剩余部分 $\text{"baaa"}$（来自 $x$）
   • 向 $y$ 追加 $\text{"baaabad"}$ 后：$x=\text{"abbaaa"}$ ， $y=\text{"abbaaabad"}$ ，共同前缀 $\text{"abbaa"}$ ，剩余部分 $\text{"abad"}$（来自 $y$）

   这样，我们只需要追踪一个字符串——当前需要匹配的剩余部分。

4. 状态转移
   设当前剩余部分为 $s$ 。当我们选择一个单词 $w$ 时，有两种情况：

   • 如果 $s$ 以 $w$ 为前缀，说明 $w$ 可以追加到当前较短的字符串上，使得较短的变长，剩余部分变为 $s$ 去掉 $w$ 前缀后的部分
   • 如果 $w$ 以 $s$ 为前缀，说明 $w$ 可以追加到当前较长的字符串上，使得较长的变长，剩余部分变为 $w$ 去掉 $s$ 前缀后的部分

   这两种情况可以统一处理：检查 $s$ 和 $w$ 是否互为前缀，如果是，则新剩余部分为较长者去掉共同前缀后的子串。

5. 最少操作次数
   问题转化为：从初始剩余部分出发，每次选择一个单词，根据上述规则转移到新的剩余部分，求到达空字符串的最少步数。这是一个典型的最短路径问题，由于每次操作代价为 $1$ ，可以用 $\text{BFS}$ 求解。

解题思路

算法步骤

1. 预处理
   读入测试用例数 $T$ 。

2. 对于每个测试用例：

   • 读入 $x$ 和 $y$
   • 检查 $x$ 和 $y$ 是否互为前缀（使用 $\text{isPrefix}$ 函数）
   • 如果不是，输出 $-1$ 并继续下一个测试用例
   • 如果是，计算初始剩余部分 $\text{remain}=\text{getRemainder}(x,y)$
   • 如果 $\text{remain}$ 为空，说明已经相同，输出 $0$ 并继续

3. $\text{BFS}$ 搜索

   • 使用队列 $\text{q}$ 存储待处理的剩余部分
   • 使用哈希表 $\text{dist}$ 记录到达每个剩余部分的最少步数
   • 初始状态：$\text{dist[remain]}=0$ ，$\text{q.push(remain)}$
   • 当队列非空：
     • 取出队首 $\text{cur}$ 及其步数 $\text{steps}$
     • 如果 $\text{cur}$ 为空，返回 $\text{steps}$
     • 遍历每个单词 $\text{w}$：
       • 如果 $\text{isPrefix(cur, w)}$ 为真（即互为前缀）
       • 计算新剩余部分 $\text{next}=\text{getRemainder(cur, w)}$
       • 如果 $\text{next}$ 未被访问过，更新距离并入队
   • 如果队列为空仍未找到空字符串，返回 $-1$

4. 输出结果

正确性证明

• 状态表示的完备性：任意时刻，两个字符串的状态可以用剩余部分唯一表示，因为共同前缀已经匹配，只需要关心后续需要匹配的部分。
• 状态转移的正确性：每次操作对应一次单词追加，必然导致剩余部分按照上述规则变化。反之，任何合法的剩余部分变化都对应一次有效操作。
• 最优性：$\text{BFS}$ 保证首次到达空字符串时的步数最小。

复杂度分析

• 时间复杂度：$O(L\cdot k\cdot |w|)$ ，其中 $L$ 是可能出现的剩余部分的最大长度，$k$ 是单词个数，$|w|$ 是单词平均长度。实际运行中状态数远小于理论最大值。
• 空间复杂度：$O(L\cdot k)$ ，用于存储 $\text{dist}$ 映射和队列。

注意事项

1. 单词可以重复使用，不需要记录使用状态。
2. 剩余部分可能很长，需要使用 $\text{string}$ 类型存储。
3. $\text{isPrefix}$ 函数需要正确处理两个字符串长度不同的情况。
4. 使用 $\text{unordered\_map}$ 而不是 $\text{map}$ 以获得更好的平均性能。

参考代码

// Words Adjustment
// UVa ID: 10941
// Verdict: Accepted
// Submission Date: 2026-03-01
// UVa Run Time: 0.060s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

// 检查 a 和 b 是否互为前缀
bool isPrefix(const string& a, const string& b) {
    int n = min(a.size(), b.size());
    for (int i = 0; i < n; i++)
        if (a[i] != b[i]) return false;
    return true;
}

// 返回较长字符串去掉共同前缀后的剩余部分
string getRemainder(const string& a, const string& b) {
    int n = min(a.size(), b.size());
    return (a.size() > b.size() ? a : b).substr(n);
}

int solve(string x, string y, vector<string>& words) {
    // 检查是否互为前缀
    if (!isPrefix(x, y)) return -1;
    
    // 获取需要匹配的剩余部分
    string remain = getRemainder(x, y);
    if (remain.empty()) return 0;
    
    // BFS：状态为当前需要匹配的剩余字符串
    unordered_map<string, int> dist;
    queue<string> q;
    
    dist[remain] = 0;
    q.push(remain);
    
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int steps = dist[cur];
        
        if (cur.empty()) return steps;
        
        for (string& w : words) {
            // 检查 w 和 cur 是否互为前缀
            if (isPrefix(cur, w)) {
                string next = getRemainder(cur, w);
                if (!dist.count(next)) {
                    dist[next] = steps + 1;
                    q.push(next);
                }
            }
        }
    }
    
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int caseNum;
    cin >> caseNum;
    
    while (caseNum--) {
        string x, y;
        cin >> x >> y;
        
        int k;
        cin >> k;
        
        vector<string> words(k);
        for (int i = 0; i < k; i++) cin >> words[i];
        
        int result = solve(x, y, words);
        cout << result << "\n";
    }
    
    return 0;
}

总结

本题的关键在于将两个字符串的状态巧妙地转化为单个剩余字符串，从而将问题简化为单源最短路径问题。这种转化思路在字符串处理问题中非常常见，值得学习掌握。$\text{BFS}$ 的使用保证了在无权图中找到最优解，而 $\text{unordered\_map}$ 则提供了高效的狀態查詢。