核心思路

本题要求通过后缀替换操作将字符串 $S$ 转换为 $T$，求最小操作次数。关键在于将问题建模为动态规划，通过状态转移计算所有可能字符串转换的最短路径。

关键观察

1. 操作特性：每次操作只能替换当前字符串的后缀，且替换前后字符串长度不变
2. 状态表示：每个字符串可以看作一个状态，替换规则构成状态间的转移边
3. 长度分层：按字符串长度分层处理，利用较短字符串的已知信息计算较长字符串的转换

重要状态定义

设 $dp[i][j][k]$ 表示：

• 字符串长度为 $i$
• 从第 $j$ 个字符串（状态）
• 转换到第 $k$ 个字符串（状态）
• 所需的最小操作步数

算法框架

状态初始化

• 长度为 $0$ 时：$dp[0][j][k] = 0$（空串到空串无需操作）
• 其他情况初始化为无穷大

状态转移

对于每个长度 $i$，考虑两种转移方式：

1. 直接替换：使用长度为 $i$ 的替换规则 $u \to v$

   $$dp[i][j][v] = \min(dp[i][j][v], dp[i][j][u] + 1)$$

2. 字符匹配：如果两个字符串在第 $i$ 位字符相同，可以利用长度 $i-1$ 的转换信息

   $$dp[i][j][k] = \min(dp[i][j][k], dp[i][j][now] + dp[i-1][now][k]) $$

   其中 $p[now][i-1] = p[k][i-1]$（第 $i$ 位字符相同）

算法流程

1. 字符串反转处理，便于从前向后匹配
2. 对所有字符串进行编号，建立映射
3. 按长度从 $1$ 到 $n$ 逐层计算
4. 每层使用 BFS 进行状态转移
5. 最终答案为 $dp[n][S][T]$

复杂度优化

• 状态压缩：字符串长度 $\leq 20$，状态数可控
• 字符索引：预处理每个位置包含特定字符的字符串集合，加速匹配
• BFS 更新：确保每次找到当前最短路径