## Leetcode 3031. Minimum Time to Revert Word to Initial State II

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 解題想法

我們可以用 KMP 算法的 LPS (Longest Prefix Suffix, 最長相等前後綴) 去做這個，然後發現一件事是答案上界是 $\lceil n/k \rceil$，其中 $n$ 是字串長度，我們每次找到一個後綴 = 前綴的，就去檢查他長度是不是對的(題目的 $k$ 限制)，直到找到對又或著是放棄(找不到乾脆暴力重弄個字串，就是上面的答案上界)。

### Code

C++

class Solution {
public:
    void LPS(int* arr, const string s){
        const int n = s.length();
        for(int i = 0; i < n; i++) arr[i] = 0;
        int prev = 0, now = 1;
        while(now != n){
            if(s[prev] == s[now]){
                arr[now] = prev + 1;
                now++;
                prev++;
            }
            else if(prev == 0){
                now++;
            }
            else{
                prev = arr[prev-1];
            }
        }
    } 
    int minimumTimeToInitialState(string word, int k) {
        const int n = word.length();
        const int inf = 1e9;
        int arr[n];
        
        LPS(arr, word);
        
        int ptr = arr[n-1];
        while(ptr > 0 && (n - ptr) % k != 0){
            ptr = arr[ptr - 1];
        }
        
        if(ptr == 0){
            return (n - 1) / k + 1;
        }
        return (n - ptr) / k;
    }
};