题目描述
给你一个下标从 0 开始的字符串 word
和一个整数 k
。
在每一秒,你必须执行以下操作:
- 移除
word
的前k
个字符。 - 在
word
的末尾添加k
个任意字符。
注意 添加的字符不必和移除的字符相同。但是,必须在每一秒钟都执行 两种 操作。
返回将 word
恢复到其 初始 状态所需的 最短 时间(该时间必须大于零)。
样例
输入:word = "abacaba", k = 3
输出:2
解释:
第 1 秒,移除 word 的前缀 "aba",并在末尾添加 "bac"。
因此,word 变为 "cababac"。
第 2 秒,移除 word 的前缀 "cab",并在末尾添加 "aba"。
因此,word 变为 "abacaba" 并恢复到始状态。
可以证明,2 秒是 word 恢复到其初始状态所需的最短时间。
输入:word = "abacaba", k = 4
输出:1
解释:
第 1 秒,移除 word 的前缀 "abac",并在末尾添加 "caba"。
因此,word 变为 "abacaba" 并恢复到初始状态。
可以证明,1 秒是 word 恢复到其初始状态所需的最短时间。
输入:word = "abcbabcd", k = 2
输出:4
解释:
每一秒,我们都移除 word 的前 2 个字符,并在 word 末尾添加相同的字符。
4 秒后,word 变为 "abcbabcd" 并恢复到初始状态。
可以证明,4 秒是 word 恢复到其初始状态所需的最短时间。
限制
1 <= word.length <= 10^5
1 <= k <= word.length
word
仅由小写英文字母组成。
算法
(KMP) $O(n)$
- 通过 KMP 算法求出前缀和后缀的最长匹配长度 $j$。
- 如果前缀和后缀没有匹配,显然返回 $\lceil \frac{n}{k} \rceil$。
- 否则,对于可以匹配的长度 $j$,如果 $n - j$ 可以被 $k$ 整除,则返回 $(n - j) / k$。否则,令 $j = nxt(j)$,即不断缩短可匹配的长度。
- 如果所有长度都无法匹配,则也返回 $\lceil \frac{n}{k} \rceil$。
时间复杂度
- KMP 构造模式串适配指针的时间复杂度为 $O(n)$。
- 匹配答案最坏情况下的时间复杂度也为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储 KMP 数组。
C++ 代码
class Solution {
public:
int minimumTimeToInitialState(string word, int k) {
const int n = word.size();
vector<int> nxt(n);
nxt[0] = -1;
int j = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && word[i] != word[j + 1])
j = nxt[j];
if (word[i] == word[j + 1])
++j;
nxt[i] = j;
}
while (j >= 0 && (n - j - 1) % k > 0)
j = nxt[j];
if (j != -1)
return (n - j - 1) / k;
return (n - 1) / k + 1;
}
};