UVa 1089 Suffix-Replacement Grammars

题目描述

给定一个后缀替换文法，包含一个起始字符串 $S$ 和一个目标字符串 $T$，以及 $NR$ 条规则，每条规则形如 $X\to Y$，其中 $X$ 和 $Y$ 是等长的字母数字字符串。应用规则时，若当前字符串的后缀恰好等于 $X$，则可将该后缀替换为 $Y$。规则可以任意多次使用。要求判断是否能从 $S$ 变换到 $T$，若能，则输出所需的最少规则应用次数。

输入格式

输入包含多个测试用例。每个测试用例以一行开始，包含两个等长的字母数字字符串 $S$ 和 $T$（长度 $1\le |S|=|T|\le 20$，由空格分隔），以及一个整数 $NR$（$0\le NR\le 100$），表示规则条数。随后 $NR$ 行，每行包含两个等长的字母数字字符串 $X$ 和 $Y$（长度 $1\le |X|=|Y|\le 20$），表示规则 $X\to Y$。所有字符串区分大小写。输入以一行单独的句点 . 结束。

输出格式

对于每个测试用例，输出一行 Case x: 后接最少规则应用次数；如果无法变换，则输出 No solution。

样例

输入

AA BB 4
A B
AB BA
AA CC
CC BB
A B 3
A C
B C
C B
.

输出

Case 1: 2
Case 2: No solution

题目分析

本题的核心是在一个状态空间（所有与 $S$ 等长的字符串）中，以规则为有向边，求从 $S$ 到 $T$ 的最短路径。然而，由于字母数字字符集大小为 $62$，长度最大为 $20$，完整状态空间理论上有 $62^{20}$ 个状态，不可能直接搜索。

但规则只能修改后缀，这一特性大大限制了状态间的转换关系。我们可以将字符串按照长度分层，仅关注可能出现的后缀。任意规则 $X\to Y$ 以及初始串 $S$ 和目标串 $T$，它们的所有后缀都有可能出现在某次变换中。因此，所有可达字符串的后缀必定在这些集合内。这样，状态数量被限制在 $O(NR\cdot L+L^2)$ 级别，其中 $L\le 20$，因此可以接受。

进一步观察，长度为 $k$ 的字符串之间，如果两个串的首字符相同，则它们的转换可以分解为：先处理首字符后的长度为 $k-1$ 的后缀（利用长度 $k-1$ 的最短路径），然后再考虑是否需替换首字符（直接规则或间接规则）。这启发我们采用动态规划思想，从长度 $1$ 开始，逐步向长度 $L$ 扩展，利用 $\text{Floyd-Warshall}$ 算法计算每一层内所有节点之间的最短距离。

解题思路

状态定义与编号

对于每个长度 $k$（$1\le k\le L$），将所有可能出现的后缀（即 $S$ 和 $T$ 的所有后缀、所有规则左右两侧的所有后缀）收集起来，去重后存入数组 suffixList[k]，并用哈希映射 idMap[k] 将每个字符串映射到其编号。这样，长度为 $k$ 的节点个数 $n_k$ 非常有限（通常不超过几百个）。

构建长度 $k$ 的转移图

对于长度为 $k$ 的任意两个节点 $i$ 和 $j$（对应字符串 $u$ 和 $v$），我们定义从 $u$ 到 $v$ 的最短距离 ${\text{dist}}_k[i][j]$。其初始值设为无穷大，对角线为 $0$。

转移分为两类：

将这些初始边加入后，对长度 $k$ 的节点集合运行 $\text{Floyd-Warshall}$ 算法，求得该层所有节点之间的最短闭包。这个闭包就表示在长度保持为 $k$ 的前提下，任意两串之间变换所需的最少规则数。

逐层递推

我们从 $k=1$ 开始，逐步计算到 $k=L$。在计算第 $k$ 层时，使用第 $k-1$ 层的结果（preDist）作为间接转移的依据。计算完成后，将该层的 dist 复制给 preDist，用于下一层的计算。

最终，当 $k=L$ 时，preDist 就是长度为 $L$ 的所有可达状态之间的最短距离矩阵。直接取出 $S$ 和 $T$ 对应的编号，其距离即为答案（若为无穷大则表示不可达）。

正确性说明

该算法的正确性基于以下观察：

• 任何对长度为 $k$ 的字符串进行操作，若操作改变了首字符，则必然是直接应用了一条规则，且该规则左右两侧长度均为 $k$（因为规则只能替换整个后缀，若替换长度小于 $k$，首字符不受影响；若替换长度为 $k$，则整个字符串被替换，首字符可能改变）。
• 若首字符不变，则只可能通过修改剩余长度为 $k-1$ 的后缀来实现，这正好对应间接转移。
• 通过 $\text{Floyd-Warshall}$ 计算闭包，可以组合多条直接或间接边，得到任意两点间的最短路径。

由于长度上限很小（$L\le 20$），各层节点总数也小，$\text{Floyd-Warshall}$ 的 $O(n_k^3)$ 是可接受的。

复杂度分析

• 收集节点：每条规则产生至多 $|X|+|Y|$ 个后缀，总共 $O(NR\cdot L)$ 个字符串，每个字符串插入哈希表 $O(L)$，故 $O(NR\cdot L^2)$。
• 每层节点数 $n_k$ 不超过 $NR\cdot L+2L$，实际很小。
• 每层 $\text{Floyd-Warshall}$ 算法的时间复杂度 $O(n_k^3)$，总复杂度为 $O({\sum }_{k=1}^L{n}_k^3)$，在最坏情况下 $L=20$，$NR=100$，$n_k$ 约为 $200$，计算量约为 $20\times 200^3=1.6\times 10^8$，在可接受范围内（实际运行很快）。
• 空间复杂度 $O(\max n_k^2)$。

代码实现

// Suffix-Replacement Grammars
// UVa ID: 1089
// Verdict: Accepted
// Submission Date: 2026-06-21
// UVa Run Time: 0.560s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int MAXL = 25;
const long long INF = (1LL << 60);

vector<string> suffixList[MAXL];
map<string, int> idMap[MAXL];

void addNode(const string& s) {
int len = s.size();
if (len >= MAXL) return;
if (idMap[len].count(s)) return;
int label = idMap[len].size();
idMap[len][s] = label;
suffixList[len].push_back(s);
}

long long solveCase(const string& S, const string& T, const vector<pair<string, string>>& rules) {
int L = S.size();
// 清空之前的数据
for (int i = 0; i < MAXL; ++i) {
suffixList[i].clear();
idMap[i].clear();
}
// 收集所有可能出现的后缀：规则 X、Y 的所有后缀，以及 S、T 的所有后缀
for (const auto& rule : rules) {
const string& X = rule.first;
const string& Y = rule.second;
for (int i = 0; i < (int)X.size(); ++i)
addNode(X.substr(i));
for (int i = 0; i < (int)Y.size(); ++i)
addNode(Y.substr(i));
}
for (int i = 0; i < L; ++i) {
addNode(S.substr(i));
addNode(T.substr(i));
}

vector<vector<long long>> preDist; // 长度 k-1 的距离矩阵

for (int k = 1; k <= L; ++k) {
int n = suffixList[k].size();
vector<vector<long long>> dist(n, vector<long long>(n, INF));
for (int i = 0; i < n; ++i) dist[i][i] = 0;

// 填充初始边
for (int i = 0; i < n; ++i) {
const string& si = suffixList[k][i];
for (int j = 0; j < n; ++j) {
const string& sj = suffixList[k][j];
// 直接规则
for (const auto& rule : rules) {
if (rule.first == si && rule.second == sj) {
dist[i][j] = min(dist[i][j], 1LL);
break;
}
}
// 间接转移：首字符相同
if (k > 1 && si[0] == sj[0]) {
string subI = si.substr(1);
string subJ = sj.substr(1);
auto itI = idMap[k – 1].find(subI);
auto itJ = idMap[k – 1].find(subJ);
if (itI != idMap[k – 1].end() && itJ != idMap[k – 1].end()) {
int pi = itI->second;
int pj = itJ->second;
dist[i][j] = min(dist[i][j], preDist[pi][pj]);
}
}
}
}

// Floyd 求传递闭包
for (int mid = 0; mid < n; ++mid)
for (int i = 0; i < n; ++i) {
if (dist[i][mid] >= INF) continue;
for (int j = 0; j < n; ++j)
if (dist[mid][j] < INF)
dist[i][j] = min(dist[i][j], dist[i][mid] + dist[mid][j]);
}

preDist = move(dist); // 作为下一长度的前驱矩阵
}

int st = idMap[L][S];
int ed = idMap[L][T];
long long ans = preDist[st][ed];
return (ans >= INF ? –1 : ans);
}

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

string S, T;
int NR;
int caseNo = 1;
while (cin >> S) {
if (S == ".") break;
cin >> T >> NR;
vector<pair<string, string>> rules;
for (int i = 0; i < NR; ++i) {
string X, Y;
cin >> X >> Y;
rules.emplace_back(X, Y);
}
long long ans = solveCase(S, T, rules);
cout << "Case " << caseNo++ << ": ";
if (ans == –1) cout << "No solution\\n";
else cout << ans << "\\n";
}
return 0;
}

总结

本题的关键在于利用规则仅作用于后缀这一限制，将状态空间压缩到所有可能出现的后缀集合。通过长度分层和动态规划，将任意长度的字符串之间的最短路径问题，分解为同一长度下的闭包计算和长度间的递推。$\text{Floyd-Warshall}$ 算法在每层内求解全源最短路径，而层间则通过首字符相同的条件进行转移。该方法有效避免了直接搜索的巨大状态空间，且实现简洁，性能优异。此类“后缀替换”问题往往可以借鉴字符串分层 $\text{DP}$ 的思路，是解决规则驱动型字符串变换问题的常用技巧。