String Transformation

Link

Description

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 smaking 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:

• 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:

• 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.

Solution

See reference (Chinese).

class Solution {
private:
    vector<int> calcMaxMatch(string s) {
        vector<int> match(s.length());
        int c = 0;
        for (int i = 1; i < s.length(); i++) {
            char v = s[i];
            while (c && s[c] != v) {
                c = match[c - 1];
            }
            if (s[c] == v) {
                c++;
            }
            match[i] = c;
        }
        return match;
    }

    int KMPSearch(string text, string pattern) {
        vector<int> match = calcMaxMatch(pattern);
        int matchCnt = 0, c = 0;
        for (int i = 0; i < text.length(); i++) {
            char v = text[i];
            while (c && pattern[c] != v) {
                c = match[c - 1];
            }
            if (pattern[c] == v) {
                c++;
            }
            if (c == pattern.length()) {
                matchCnt++;
                c = match[c - 1];
            }
        }
        return matchCnt;
    }

    const long long MOD = 1e9 + 7;

    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));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD;
            }
        }
        return c;
    }

    vector<vector<long long>> pow(vector<vector<long long>>& a, long long n) {
        vector<vector<long long>> res = {{1, 0}, {0, 1}};
        for (; n; n /= 2) {
            if (n % 2) {
                res = multiply(res, a);
            }
            a = multiply(a, a);
        }
        return res;
    }

public:
    int numberOfWays(string s, string t, long long k) {
        int n = s.length();
        int c = KMPSearch(s + s.substr(0, n - 1), t);
        vector<vector<long long>> m = {
            {c - 1, c},
            {(n - 1) - (c - 1), (n - 1) - c}
        };

        m = pow(m, k);
        return m[0][s != t];
    }
};

• Time complexity: \(O(n+\log k)\), where \(n\) is the length of \(s\);
• Space complexity: \(O(n)\).