字符串转换

Leetcode题目链接

描述

详见中文题目链接。

解答

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];
    }
};