2851. 字符串转换(2858)

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

  • 将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
    比方说，s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。

给你一个整数 k ，请你返回 恰好 k 次操作将 s 变为 t 的方案数。

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：s = "abcd", t = "cdab", k = 2
输出：2
解释：
第一种方案：
第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。
第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。

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

示例 2：

1
2
3
4
5
6
7
8
输入：s = "ababab", t = "ababab", k = 1
输出：2
解释：
第一种方案：
选择 index = 2 开始的后缀，得到 s = "ababab" 。

第二种方案：
选择 index = 4 开始的后缀，得到 s = "ababab" 。

提示：

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

动态规划+矩阵快速幂

对于长度为n的字符串s，总共有n-1个切割位置

若切片旋转后的字符串变为t，则令duplication times += 1
duplication times 简写为 d

例一: d = 1

例二: d = 3

用f(i,0)表示：在第i次操作后，将字符串变为t

用f(i,1)表示：在第i次操作后，将字符串变为非t

  • 如果操作后是t
    • 如果上一步是t，那么有 d-1 种操作方案
    • 如果上一步不是t，那么有 d 种操作方案

f(i,0) = f(i-1,0)*(d-1) + f(i-1,1)*d

  • 如果操作后不是t
    • 如果上一步是t，那么有 n-1-(d-1) 种操作方案
    • 如果上一步不是t，那么有 n-1-d 种操作方案

f(i,1) = f(i-1,0)*(n-d) + f(i-1,1)*(n-1-d)

用矩阵乘来表示上述转移方程

1
2
f(i,0) = [d-1     d]  f(i-1,0)
f(i,1) = [n-d n-1-d]  f(i-1,1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Solution {
    // KMP 模板
    private int[] calcMaxMatch(String s) {
        int[] match = new int[s.length()];
        int c = 0;
        for (int i = 1; i < s.length(); i++) {
            char v = s.charAt(i);
            while (c > 0 && s.charAt(c) != v) {
                c = match[c - 1];
            }
            if (s.charAt(c) == v) {
                c++;
            }
            match[i] = c;
        }
        return match;
    }
    // KMP 模板
    // 返回 text 中出现了多少次 pattern（允许 pattern 重叠）
    private int kmpSearch(String text, String pattern) {
        int[] match = calcMaxMatch(pattern);
        int lenP = pattern.length();
        int matchCnt = 0;
        int c = 0;
        for (int i = 0; i < text.length(); i++) {
            char v = text.charAt(i);
            while (c > 0 && pattern.charAt(c) != v) {
                c = match[c - 1];
            }
            if (pattern.charAt(c) == v) {
                c++;
            }
            if (c == lenP) {
                matchCnt++;
                c = match[c - 1];
            }
        }
        return matchCnt;
    }

    public int numberOfWays(String s, String t, long k) {
        int n = s.length(), d = 0;
        String tg = s + s.substring(0, n-1);
        // for (int i = 0; i < n; i++) {
        //     String cur = tg.substring(i, i+n);
        //     if (cur.equals(t)) d += 1;
        // }
        d = kmpSearch(tg, t);
        int f0[] = new int[2];
        if (s.equals(t)) {
            f0[0] = 1; f0[1] = 0;
        }
        else {
            f0[0] = 0; f0[1] = 1;
        }
        long matrix[][] = new long[][]{{d-1, d}, {n-d, n-1-d}};
        long res[][] = pow(matrix, k);
        if (f0[0] == 1) return (int)res[0][0];
        else return (int)res[0][1];
    }
    int MOD = (int)1e9+7;
    public long[][] pow(long matrix[][], long k) {
        long res[][] = new long[][]{{1,0},{0,1}};
        if (k == 0) return res;
        long newMatrix[][] = multi(matrix, matrix, 2);
        res = pow(newMatrix, k/2);
        if (k % 2 == 1) {
            res = multi(res, matrix, 2);
        }
        return res;
    }
    public long[][] multi(long a[][], long b[][], int n) {
        long res[][] = new long[n][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                    res[i][j] %= MOD;
                }
            }
        }
        return res;
    }
}