千问 LeetCode 2851. 字符串转换 Java实现

稚辉君.MCA.P9.JAVA

223人浏览 · 2026-05-31 19:31:37

稚辉君.MCA.P9.JAVA · 2026-05-31 19:31:37 发布

这道题是 LeetCode 2851 题，是一道结合了 KMP字符串匹配、动态规划（DP）和矩阵快速幂的困难级题目。

核心思路解析

1. 字符串循环同构（KMP算法）
每次操作是将字符串 s 的一个后缀移到开头，这实际上是在对字符串进行循环移位。我们需要知道，s 的所有循环移位结果中，有多少种能够变成目标字符串 t。
为了高效地找出这些匹配位置，我们将 s 复制一份拼接到自己后面（即 s + s），然后使用 KMP 算法在 s + s 中查找 t 出现的所有位置。假设一共有 match 个位置可以匹配成功。

2. 状态定义与动态规划
设字符串长度为 n。我们可以定义两个状态：
* f[i]：经过 i 次操作后，字符串恰好变为 t 的方案数。
* g[i]：经过 i 次操作后，字符串没有变为 t 的方案数。

状态转移逻辑如下：
* 如果当前已经是 t（状态 f），下一次操作有 match - 1 种方式保持为 t（不能原地不动，所以要减1），有 n - match 种方式变成非 t。
* 如果当前不是 t（状态 g），下一次操作有 match 种方式变成 t，有 n - 1 - match 种方式保持为非 t。

由此得出转移方程：
f[i] = f[i-1] * (match - 1) + g[i-1] * match
g[i] = f[i-1] * (n - match) + g[i-1] * (n - 1 - match)

3. 矩阵快速幂优化
题目中 k 的最大值高达 10^15，普通的循环递推肯定会超时。由于上述 DP 转移方程是线性的，我们可以将其转化为矩阵乘法的形式，并使用矩阵快速幂在 O(log k) 的时间复杂度内求出结果。

Java 代码实现

class Solution {
private static final int MOD = 1000000007;

public int numberOfWays(String s, String t, long k) {
int n = s.length();

// 1. 使用 KMP 算法计算 s 的循环移位中有多少个能匹配 t
int match = kmpSearch(s, t);

// 2. 初始化 DP 状态
// f 表示当前等于 t 的方案数，g 表示当前不等于 t 的方案数
long f, g;
if (s.equals(t)) {
f = 1;
g = 0;
} else {
f = 0;
g = 1;
}

// 3. 构建转移矩阵
// [f[i], g[i]] = [f[i-1], g[i-1]] * Matrix
// Matrix = [[match - 1, n - match],
// [match, n - 1 - match]]
long[][] matrix = {
{(match - 1 + MOD) % MOD, (n - match + MOD) % MOD},
{match, (n - 1 - match + MOD) % MOD}
};

// 4. 矩阵快速幂计算 k 次转移后的结果
long[][] resultMatrix = matrixPower(matrix, k);

// 5. 计算最终答案 f[k]
// [f[k], g[k]] = [f[0], g[0]] * resultMatrix
long ans = (f * resultMatrix[0][0] + g * resultMatrix[1][0]) % MOD;
return (int) ans;
}

// KMP 算法：在 s+s 中查找 t 的出现次数
private int kmpSearch(String s, String t) {
int n = s.length();
int[] next = computeNext(t);
int matchCount = 0;
int j = 0; // t 的指针

// 在 s + s 中匹配，但只需要遍历到 2n - 1 即可
for (int i = 0; i < 2 * n - 1; i++) {
char currentS = s.charAt(i % n);
while (j > 0 && t.charAt(j) != currentS) {
j = next[j - 1];
}
if (t.charAt(j) == currentS) {
j++;
}
if (j == n) {
matchCount++;
j = next[j - 1];
}
}
return matchCount;
}

// 计算 KMP 的 next 数组
private int[] computeNext(String pattern) {
int n = pattern.length();
int[] next = new int[n];
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}

// 2x2 矩阵乘法
private long[][] multiply(long[][] a, long[][] b) {
long[][] c = new long[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}

// 矩阵快速幂
private long[][] matrixPower(long[][] matrix, long power) {
// 初始化为单位矩阵 [[1, 0], [0, 1]]
long[][] result = {{1, 0}, {0, 1}};
long[][] base = matrix;

while (power > 0) {
if ((power & 1) == 1) {
result = multiply(result, base);
}
base = multiply(base, base);
power >>= 1;
}
return result;
}
}