Hard

题目描述

给你两个长度相等的字符串 s 和 t，长度为 n。你可以对字符串 s 执行以下操作：

  • 移除 s 的一个长度为 l 的后缀，其中 0 < l < n，并将其添加到 s 的开头。
  • 例如，设 s = "abcd"，那么在一次操作中，你可以移除后缀 "cd" 并将其添加到 s 的前面，使 s = "cdab"。

同时给你一个整数 k。返回在恰好 k 次操作中将 s 转换为 t 的方案数。

由于答案可能很大，返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：s = "abcd", t = "cdab", k = 2
输出：2
解释：
第一种方法：
第一次操作，选择从索引 3 开始的后缀，得到 s = "dabc"。
第二次操作，选择从索引 3 开始的后缀，得到 s = "cdab"。

第二种方法：
第一次操作，选择从索引 1 开始的后缀，得到 s = "bcda"。
第二次操作，选择从索引 1 开始的后缀，得到 s = "cdab"。

示例 2：

输入：s = "ababab", t = "ababab", k = 1
输出：2
解释：
第一种方法：
选择从索引 2 开始的后缀，得到 s = "ababab"。

第二种方法：
选择从索引 4 开始的后缀，得到 s = "ababab"。

约束条件：

  • 2 <= s.length <= 5 * 10^5
  • 1 <= k <= 10^15
  • s.length == t.length
  • s 和 t 只包含小写英文字母。

解题思路

这道题的关键insight是：如果字符串 t 可以由字符串 s 通过旋转操作得到，那么 t 必定是 s+s 的子串。

首先需要检查 t 是否为 s 的旋转版本。如果不是，则答案为 0。

接下来使用 Z 算法或 KMP 算法找出所有使得 s 旋转后等于 t 的旋转位置数量，记为 c。

然后这个问题转化为动态规划问题：

  • 设 dp[i][0] 表示经过 i 次操作后，字符串不等于 t 的方案数
  • 设 dp[i][1] 表示经过 i 次操作后，字符串等于 t 的方案数

状态转移方程：

  • dp[i][0] = dp[i-1][0] * (n-1-c) + dp[i-1][1] * (n-1-c)
  • dp[i][1] = dp[i-1][0] * c + dp[i-1][1] * c

由于 k 可能很大（10^15），需要使用矩阵快速幂来优化计算。

转移矩阵为：

[n-1-c  c  ]
[n-1-c  c  ]

初始状态：如果 s == t，则 dp[0] = [0, 1]，否则 dp[0] = [1, 0]。

代码实现

class Solution {
public:
    const int MOD = 1e9 + 7;
    
    vector<int> computeZ(string s) {
        int n = s.length();
        vector<int> z(n);
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r) z[i] = min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
            if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
        }
        return z;
    }
    
    vector<vector<long long>> multiply(vector<vector<long long>>& A, vector<vector<long long>>& B) {
        vector<vector<long long>> C(2, vector<long long>(2, 0));
        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;
    }
    
    vector<vector<long long>> matrixPower(vector<vector<long long>> mat, long long k) {
        vector<vector<long long>> result = {{1, 0}, {0, 1}};
        while (k > 0) {
            if (k & 1) result = multiply(result, mat);
            mat = multiply(mat, mat);
            k >>= 1;
        }
        return result;
    }
    
    int numberOfWays(string s, string t, long long k) {
        int n = s.length();
        
        if ((s + s).find(t) == string::npos) return 0;
        
        string combined = t + "#" + s + s;
        vector<int> z = computeZ(combined);
        
        int c = 0;
        for (int i = n + 1; i < 2 * n + 1; i++) {
            if (z[i] >= n) c++;
        }
        
        vector<vector<long long>> trans = {{n - 1 - c, c}, {n - 1 - c, c}};
        vector<vector<long long>> result = matrixPower(trans, k);
        
        if (s == t) {
            return result[1][1];
        } else {
            return result[0][1];
        }
    }
};

class Solution:
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        
        def compute_z(s):
            n = len(s)
            z = [0] * n
            l, r = 0, 0
            for i in range(1, n):
                if i <= r:
                    z[i] = min(r - i + 1, z[i - l])
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
                if i + z[i] - 1 > r:
                    l, r = i, i + z[i] - 1
            return z
        
        if t not in s + s:
            return 0
        
        combined = t + "#" + s + s
        z = compute_z(combined)
        
        c = 0
        for i in range(n + 1, 2 * n + 1):
            if z[i] >= n:
                c += 1
        
        def matrix_multiply(A, B):
            return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD,
                     (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD],
                    [(A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD,
                     (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD]]
        
        def matrix_power(mat, k):
            result = [[1, 0], [0, 1]]
            while k > 0:
                if k & 1:
                    result = matrix_multiply(result, mat)
                mat = matrix_multiply(mat, mat)
                k >>= 1
            return result
        
        trans = [[n - 1 - c, c], [n - 1 - c, c]]
        result = matrix_power(trans, k)
        
        if s == t:
            return result[1][1]
        else:
            return result[0][1]

public class Solution {
    private const int MOD = 1000000007;
    
    private int[] ComputeZ(string s) {
        int n = s.Length;
        int[] z = new int[n];
        for (int i = 1, l = 0, r = 0; i < n; i++) {
            if (i <= r) z[i] = Math.Min(r - i + 1, z[i - l]);
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
    
    private long[,] MatrixMultiply(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[,] mat, long k) {
        long[,] result = {{1, 0}, {0, 1}};
        while (k > 0) {
            if ((k & 1) == 1) result = MatrixMultiply(result, mat);
            mat = MatrixMultiply(mat, mat);
            k >>= 1;
        }
        return result;
    }
    
    public int NumberOfWays(string s, string t, long k) {
        int n = s.Length;
        
        if (!(s + s).Contains(t)) return 0;
        
        string combined = t + "#" + s + s;
        int[] z = ComputeZ(combined);
        
        int c = 0;
        for (int i = n + 1; i < 2 * n + 1; i++) {
            if (z[i] >= n) c++;
        }
        
        long[,] trans = {{n - 1 - c, c}, {n - 1 - c, c}};
        long[,] result = MatrixPower(trans, k);
        
        if (s == t) {
            return (int)result[1, 1];
        } else {
            return (int)result[0, 1];
        }
    }
}

var numberOfWays = function(s, t, k) {
    const MOD = 1000000007;
    const n = s.length;
    
    // Find all valid rotations
    const concat = s + s;
    let validRotations = 0;
    let targetRotation = -1;
    
    for (let i = 1; i < n; i++) {
        if (concat.substring(i, i + n) === t) {
            validRotations++;
            if (targetRotation === -1) {
                targetRotation = i;
            }
        }
    }
    
    if (s === t) {
        validRotations++;
        targetRotation = 0;
    }
    
    if (validRotations === 0) return 0;
    
    // Matrix exponentiation for transition matrix
    // dp[i][0] = ways to be at starting position after i operations
    // dp[i][1] = ways to be at any valid non-starting position after i operations
    
    const matMul = (a, b) => {
        return [
            [(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD,
             (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD],
            [(a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD,
             (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD]
        ];
    };
    
    const matPow = (mat, p) => {
        let result = [[1, 0], [0, 1]]; // identity matrix
        let base = mat;
        
        while (p > 0) {
            if (p % 2 === 1) {
                result = matMul(result, base);
            }
            base = matMul(base, base);
            p = Math.floor(p / 2);
        }
        
        return result;
    };
    
    if (s === t) {
        // Transition matrix: from start can go to (validRotations-1) valid positions
        // from any valid non-start position can go to start or (validRotations-2) other valid positions
        const transitionMatrix = [
            [0, validRotations - 1],
            [1, validRotations - 2]
        ];
        
        const result = matPow(transitionMatrix, k);
        return result[0][0];
    } else {
        // s !== t, we need to end at a valid rotation that equals t
        const transitionMatrix = [
            [0, validRotations],
            [1, validRotations - 1]
        ];
        
        const result = matPow(transitionMatrix, k);
        return result[0][1];
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + log k)，其中 n 为字符串长度。Z 算法需要 O(n) 时间，矩阵快速幂需要 O(log k) 时间
空间复杂度O(n)，主要用于存储 Z 数组和矩阵运算的临时空间