class Solution {
public:
int numberOfWays(string s, string t, long long k) {
}
};
8020. 字符串转换
给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作：
s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。给你一个整数 k ，请你返回 恰好 k 次操作将 s 变为 t 的方案数。
由于答案可能很大，返回答案对 109 + 7 取余 后的结果。
示例 1：
输入：s = "abcd", t = "cdab", k = 2 输出：2 解释： 第一种方案： 第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。 第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。 第二种方案： 第一次操作，选择 index = 1 开始的后缀，得到 s = "bcda" 。 第二次操作，选择 index = 1 开始的后缀，得到 s = "cdab" 。
示例 2：
输入：s = "ababab", t = "ababab", k = 1 输出：2 解释： 第一种方案： 选择 index = 2 开始的后缀，得到 s = "ababab" 。 第二种方案： 选择 index = 4 开始的后缀，得到 s = "ababab" 。
提示：
2 <= s.length <= 5 * 1051 <= k <= 1015s.length == t.lengths 和 t 都只包含小写英文字母。原站题解
javascript 解法, 执行用时: 180 ms, 内存消耗: 75.5 MB, 提交时间: 2023-09-11 06:30:17
/**
* @param {string} s
* @param {string} t
* @param {number} k
* @return {number}
*/
var numberOfWays = function (s, t, k) {
const n = s.length;
const c = kmpSearch(s + s.substring(0, n - 1), t);
const m = [
[BigInt(c - 1), BigInt(c)],
[BigInt(n - c), BigInt(n - 1 - c)],
];
const res = pow(m, k);
return s === t ? res[0][0] : res[0][1];
};
// KMP 模板
function calcMaxMatch(s) {
const match = new Array(s.length).fill(0);
let c = 0;
for (let i = 1; i < s.length; i++) {
const v = s.charAt(i);
while (c && s.charAt(c) !== v) {
c = match[c - 1];
}
if (s.charAt(c) === v) {
c++;
}
match[i] = c;
}
return match;
}
// KMP 模板
// 返回 text 中出现了多少次 pattern（允许 pattern 重叠）
function kmpSearch(text, pattern) {
const match = calcMaxMatch(pattern);
let matchCnt = 0;
let c = 0;
for (let i = 0; i < text.length; i++) {
const v = text.charAt(i);
while (c && pattern.charAt(c) !== v) {
c = match[c - 1];
}
if (pattern.charAt(c) === v) {
c++;
}
if (c === pattern.length) {
matchCnt++;
c = match[c - 1];
}
}
return matchCnt;
}
// 矩阵乘法
function multiply(a, b) {
const c = [[0, 0], [0, 0]]
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % BigInt(1e9 + 7);
}
}
return c;
}
// 矩阵快速幂
function pow(a, n) {
let res = [[BigInt(1), BigInt(0)], [BigInt(0), BigInt(1)]];
while (n) {
if (n % 2) {
res = multiply(res, a);
}
a = multiply(a, a);
n = Math.floor(n / 2);
}
return res;
}
golang 解法, 执行用时: 36 ms, 内存消耗: 11.7 MB, 提交时间: 2023-09-11 06:30:03
const mod = 1_000_000_007
type matrix [][]int
func newMatrix(n, m int) matrix {
a := make(matrix, n)
for i := range a {
a[i] = make([]int, m)
}
return a
}
func newIdentityMatrix(n int) matrix {
a := make(matrix, n)
for i := range a {
a[i] = make([]int, n)
a[i][i] = 1
}
return a
}
func (a matrix) mul(b matrix) matrix {
c := newMatrix(len(a), len(b[0]))
for i, row := range a {
for j := range b[0] {
for k, v := range row {
c[i][j] = (c[i][j] + v*b[k][j]) % mod
}
}
}
return c
}
func (a matrix) pow(n int64) matrix {
res := newIdentityMatrix(len(a))
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res.mul(a)
}
a = a.mul(a)
}
return res
}
func numberOfWays(s, t string, k int64) int {
n := len(s)
calcMaxMatchLengths := func(s string) []int {
match := make([]int, len(s))
for i, c := 1, 0; i < len(s); i++ {
v := s[i]
for c > 0 && s[c] != v {
c = match[c-1]
}
if s[c] == v {
c++
}
match[i] = c
}
return match
}
kmpSearch := func(text, pattern string) (cnt int) {
match := calcMaxMatchLengths(pattern)
lenP := len(pattern)
c := 0
for i, v := range text {
for c > 0 && pattern[c] != byte(v) {
c = match[c-1]
}
if pattern[c] == byte(v) {
c++
}
if c == lenP {
if i-lenP+1 < n {
cnt++
}
c = match[c-1]
}
}
return
}
c := kmpSearch(s+s, t)
m := matrix{
{c - 1, c},
{n - c, n - 1 - c},
}.pow(k)
if s == t {
return m[0][0]
}
return m[0][1]
}
cpp 解法, 执行用时: 144 ms, 内存消耗: 56.7 MB, 提交时间: 2023-09-11 06:29:33
class Solution {
public:
int numberOfWays(string s, string t, long long k) {
int n = s.length();
int c = kmp_search(s + s.substr(0, n - 1), t);
vector<vector<long long>> m = {
{c - 1, c},
{n - c, n - 1 - c}
};
m = pow(m, k);
return m[0][s != t];
}
private:
// KMP 模板
vector<int> calc_max_match(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;
}
// KMP 模板
// 返回 text 中出现了多少次 pattern（允许 pattern 重叠）
int kmp_search(string text, string pattern) {
vector<int> match = calc_max_match(pattern);
int match_cnt = 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()) {
match_cnt++;
c = match[c - 1];
}
}
return match_cnt;
}
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;
}
};
java 解法, 执行用时: 44 ms, 内存消耗: 52.9 MB, 提交时间: 2023-09-11 06:29:20
class Solution {
public int numberOfWays(String s, String t, long k) {
int n = s.length();
int c = kmpSearch(s + s.substring(0, n - 1), t);
long[][] m = {
{c - 1, c},
{n - c, n - 1 - c},
};
m = pow(m, k);
return s.equals(t) ? (int) m[0][0] : (int) m[0][1];
}
// 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;
}
private static final long MOD = (long) 1e9 + 7;
// 矩阵乘法
private long[][] multiply(long[][] a, long[][] b) {
long[][] c = new long[2][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;
}
// 矩阵快速幂
private long[][] pow(long[][] a, long n) {
long[][] res = {{1, 0}, {0, 1}};
for (; n > 0; n /= 2) {
if (n % 2 > 0) {
res = multiply(res, a);
}
a = multiply(a, a);
}
return res;
}
}
python3 解法, 执行用时: 1004 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-11 06:29:05
class Solution:
def numberOfWays(self, s, t, k):
n = len(s)
c = self.kmp_search(s + s[:-1], t)
m = [
[c - 1, c],
[n - c, n - 1 - c]
]
m = self.pow(m, k)
return m[0][s != t]
# KMP 模板
def calc_max_match(self, s: str) -> List[int]:
match = [0] * len(s)
c = 0
for i in range(1, len(s)):
v = s[i]
while c and s[c] != v:
c = match[c - 1]
if s[c] == v:
c += 1
match[i] = c
return match
# KMP 模板
# 返回 text 中出现了多少次 pattern（允许 pattern 重叠）
def kmp_search(self, text: str, pattern: str) -> int:
match = self.calc_max_match(pattern)
match_cnt = c = 0
for i, v in enumerate(text):
v = text[i]
while c and pattern[c] != v:
c = match[c - 1]
if pattern[c] == v:
c += 1
if c == len(pattern):
match_cnt += 1
c = match[c - 1]
return match_cnt
# 矩阵乘法
def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (10 ** 9 + 7)
return c
# 矩阵快速幂
def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
res = [[1, 0], [0, 1]]
while n:
if n % 2:
res = self.multiply(res, a)
a = self.multiply(a, a)
n //= 2
return res