字符串转换

发表于 更新于 分类于

    2851. 字符串转换

    You are given two strings s and t of equal length n. You can perform the following operation on the string s:

    • Remove a suffix of s of length l where 0 < l < n and append it at the start of s.

      For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

    You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

    Since the answer can be large, return it modulo 10^9 + 7.

    Example 1:

    ```txt

    Input: s = "abcd", t = "cdab", k = 2

    Output: 2

    Explanation:

    First way:

    In first operation, choose suffix from index = 3, so resulting s = "dabc".

    In second operation, choose suffix from index = 3, so resulting s = "cdab".

    Second way:

    In first operation, choose suffix from index = 1, so resulting s = "bcda".

    In second operation, choose suffix from index = 1, so resulting s = "cdab".

    ```

    Example 2:

    ```txt

    Input: s = "ababab", t = "ababab", k = 1

    Output: 2

    Explanation:

    First way:

    Choose suffix from index = 2, so resulting s = "ababab".

    Second way:

    Choose suffix from index = 4, so resulting s = "ababab".

    ```

    Constraints:

    • 2 <= s.length <= 5 * 10^5

    • 1 <= k <= 10^15

    • s.length == t.length

    • s and t consist of only lowercase English alphabets.

题目

2851. 字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

  • Remove a suffix of s of length l where 0 < l < n and append it at the start of s.
    For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: s = "abcd", t = "cdab", k = 2
Output: 2
Explanation: 
First way:
In first operation, choose suffix from index = 3, so resulting s = "dabc".
In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:
In first operation, choose suffix from index = 1, so resulting s = "bcda".
In second operation, choose suffix from index = 1, so resulting s = "cdab".

Example 2:

1
2
3
4
5
6
7
8
Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation: 
First way:
Choose suffix from index = 2, so resulting s = "ababab".

Second way:
Choose suffix from index = 4, so resulting s = "ababab".

Constraints:

  • 2 <= s.length <= 5 * 10^5
  • 1 <= k <= 10^15
  • s.length == t.length
  • s and t consist of only lowercase English alphabets.

题解

方法一：

思路

综合题：字符串匹配，动态规划计数，常系数递推式转化矩阵快速幂优化。

设s和t的长度都是n。

观察发现，对于s每次移动共有n-1种方式。

我们可以计算这n-1种方式形成t的个数cnt。计算的方式就是在s+s[:-1]中寻找t的出现次数。可以用各种字符串匹配算法，如kmp，字符串哈希，后缀数组等。

s总共有n种形态，实际上这n种形态中，如果s已经等于t那么就有cnt-1种方式再次转化为s，而如果s不等于t那么就有cnt种方式转化为s。这是我们dp状态转移的依据；如果s已经等于t那么就有n-1-(cnt-1)=n-cnt种方式再次转化为非s，而如果s不等于t那么就有n-1-cnt种方式转化为非s。这是我们dp状态转移的依据；

设状态$f_{i,j}$为进行i次操作后是否（j=1是，j=0否）成为t。

$f_{i, 0} = f_{i-1, 0}\times (n-1-cnt) + f_{i-1, 1}\times (n-cnt)$

$f_{i, 1} = f_{i-1, 0}\times cnt + f_{i-1, 1}\times (cnt-1)$

将递推式改为矩阵形式。

$\left[ \begin{array}{cc} f_{i, 0} & f_{i,1} \end{array} \right] = \left[ \begin{array}{cc} f_{i-1, 0} & f_{i-1,1} \end{array} \right] \left[ \begin{array}{cc} n-cnt-1 & cnt \ n-cnt & cnt-1 \end{array} \right]$

利用矩阵快速幂，求矩阵k次幂，只需$O(logk)$次矩阵乘法

$\left[ \begin{array}{cc} f_{k, 0} & f_{k,1} \end{array} \right] = \left[ \begin{array}{cc} f_{0, 0} & f_{0,1} \end{array} \right] \left[ \begin{array}{cc} n-cnt-1 & cnt \ n-cnt & cnt-1 \end{array} \right]^k$

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#define N 5
const int MOD = 1e9+7;

struct Matrix {
    int mat[N][N];
    int n;
    Matrix(int n) : n(n) { memset(mat, 0, sizeof(mat)); }
    inline void operator*=(const Matrix& o) {
        int ans[n][n];
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j])
                    for (int k = 0; k < n; k++)
                        ans[i][k] =
                            (ans[i][k] + (long long)(mat[i][j]) * o.mat[j][k]) %
                            MOD;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                mat[i][j] = ans[i][j];
    }
    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << mat[i][j] << " ";
            }
            cout << "\n";
        }
    }
};
/*
    // a *= b^n
    for (; n; n >>= 1, b *= b)
        if (n & 1)
            a *= b;
    a.print();
*/
class Solution {
public:

    void getlps(string& pat, int *lps) {
        int n = pat.size();
        lps[0] = 0;
        int i = 1, len = 0;
        while (i < n) {
            if (pat[i] == pat[len]) lps[i++] = ++len; 
            else {
                if (len != 0) len = lps[len - 1];
                else lps[i++] = 0;
            }
        }
    }

    int KMPSearch(string& pat, string& txt) {
        int m = pat.size(), n = txt.size();
        int lps[m];
        getlps(pat, lps);
        int cnt = 0;
        int i = 0, j = 0;
        while (i < n) {
            if (pat[j] == txt[i]) {
                j++; i++;
            }
            if (j == m) {
                // printf("Found pattern at index %d \n", i - j);
                cnt++;
                j = lps[j - 1];
            } else if (i < n && pat[j] != txt[i]) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return cnt;
    }
    // using ull = unsigned long long;
    // int Search(string& pat, string& txt) {
    //     int n = pat.size(), m = txt.size();
    //     const ull MOD = 998244353, BASE = 171;
    //     ull M = 0, H = 0, B = 1;
    //     for (int i=0; i<n; i++) {
    //         B = B*BASE%MOD;
    //         M = (M*BASE%MOD+pat[i])%MOD;
    //     }
    //     int cnt = 0;
    //     for (int i=0; i<=m; i++) {
    //         if(i < m) H = (H*BASE%MOD + txt[i])%MOD;
    //         if (i>=n) {
    //             H = (H-B*txt[i-n]%MOD+MOD)%MOD;
    //         }
    //         if (H == M) {
    //             // cout << i-n+1 << "匹配成功\n";
    //             cnt++;
    //         }
    //     }
    //     return cnt;
    // }
    int numberOfWays(string s, string t, long long k) {
        string s2 = s + s;
        s2.pop_back();
        int cnt = KMPSearch(t, s2);
        // f[i][j] 操作i次能成为（j=1）t的方案数。
        // f[0][0] = s!=t;
        // f[0][1] = 1-f[0][0];
        // f[i][0] = f[i-1][0]*(n-cnt-1) + f[i-1][1]*(n-cnt)
        // f[i][1] = f[i-1][0]*cnt + f[i-1][1]*(cnt-1)
        // (f[i][0] f[i][1]) = (f[i-1][0], f[i-1][1]) |n-cnt-1 cnt  |
        //                                            |n-cnt   cnt-1|
        int n = s.size();
        Matrix a(2), b(2);
        a.mat[0][0] = s!=t; a.mat[0][1] = 1-a.mat[0][0];
        b.mat[0][0] = n-cnt-1; b.mat[0][1] = cnt;
        b.mat[1][0] = n-cnt; b.mat[1][1] = cnt-1;
        // a *= b^n
        for (; k; k >>= 1, b *= b)
            if (k & 1)
                a *= b;
        // a.print();
        return a.mat[0][1];
    }
};