LC 3031. 将单词恢复初始状态所需的最短时间 II

https://leetcode.cn/problems/minimum-time-to-revert-word-to-initial-state-ii/description/

这题其实可以先从简单的版本开始做 https://leetcode.cn/problems/minimum-time-to-revert-word-to-initial-state-i/description/ 其实这题就是在找后缀的最长匹配，但是后缀的边界是在k个字符上。后面补上的字符其实完全可以根据之前匹配的情况进行补全。

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        i, ans = 0, 0
        n = len(word)
        while i < n:
            i += k
            ans += 1
            if i < n and word[:n - i] == word[i:]:
                break
        return ans

对于小数据量版本，完全可以直接使用字符串检查的方式。但是如果字符串很长的话，那么每次检查字符串相等就比较耗时。一个办法是使用rolling hash function来做，另外一个则是使用类似kmp的算法。

这里如果使用kmp算法则需要稍微做一些改进，因为我们每次选择的后缀边界是在k个字符上。一个简单做法就是，我们可以先对k个字符进行group(最后一个group可能不是k个字符)，然后使用kmp来比较每个group. 假设我们kmp算法得到的是 `max_match[i]` 表示i group的匹配前缀的最长长度是多少，那么答案就是 `len(max_match) - max_match[-1]`.

比如假设 max_match 的值是 [0,1,2,1,2,3] 的话，最后一个max_match[-1]是3，表示和前缀可以匹配3个groups, 那么说明向前数3个group可以完全可以前缀进行匹配，答案就是3.

class KMP:
    @staticmethod
    def build_max_match(t):
        n = len(t)
        match = [0] * n
        c = 0

        def eq(a, b):
            sz = min(len(a), len(b))
            return a[:sz] == b[:sz]

        for i in range(1, n):
            v = t[i]
            while c and not eq(t[c], v):
                c = match[c - 1]
            if eq(t[c], v):
                c += 1
            match[i] = c
        return match


class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        w = []
        i = 0
        while i < len(word):
            w.append(word[i:i + k])
            i += k
        match = KMP.build_max_match(w)
        ans = len(match) - match[-1]
        return ans