研究这个的动机是因为 https://leetcode.com/problems/longest-happy-prefix/ 这个周赛题不会

然后看了很多网上讲解 KMP 的博客，发现还是不理解。 因为很多到了求“最长相等前后缀”这一步就略过了或者讲的不好理解。

这里 next[i] 等于 s[0..i] 这个子串的最长相等前后缀。 目的是希望根据 next[0..i] 和 s[0..i+1] 求 next[i+1]

因为 s[0...next[i]] == s[(i-next[i]+1)..i]，所以当 s[next[i]] == s[i+1] 的时候，我们找到了匹配，有 next[i+1] = next[i] + 1 。

比如 "ccbccc" 这个字符串有 next = [0, 1, 0, 1, 2, 2]，考察 i = 3 时，next[3] == 1, s[1] == 'c' == s[4]，所以 next[4] = next[3] + 1 = 2。

难点是如果 s[next[i]] != s[i+1]，应该如何计算 next[i+1]。 首先显然 next[i+1] 会小于等于 next[i]。即如果有匹配，s[i+1] 会匹配上 s[0...next[i]] 之间的某一个字符，也就是

匹配的位置会向前移动

问题是移到哪个位置 j，可以确保 s[0...j] == s[(i-j+1)..i] 且 j 最大，这样可以再次通过比较 s[j] 和 s[i+1] 来确定 next[i+1] 的值。

s[0...j] 是 s[0..i] 的一个前缀，s[(i-j+1)..i] 是 s[0..i] 的一个后缀，且满足 s[0...j] == s[(i-j+1)..i]，j < next[i]

换句话说，我希望找到s[0..i]的一个第二长的相等前后缀来尝试匹配，如果不匹配，就尝试找第三长的，最后可能和 s 的第一个字符比较。

s[0..i]最长的相等前后缀长度是 next[i]，次长是什么呢？

应该是 s[0...next[i]] 的最长相等前后缀的长度

代换一下变量，s[0...next[i]] == s[0..(next[i] - 1)] => 次长为 next[next[i] - 1] => j = next[next[i] - 1]

第三长的为 s[0...next[next[i] - 1]] 的最长相等前后缀的长度

以此类推

j = next[next[i] - 1] // 第二长
j = next[j - 1]  // 第三长

比如 "ccbccc" 这个字符串有 next = [0, 1, 0, 1, 2, 2]，考察 i = 4 时，next[4] == 2, s[2] == 'b' != s[5]，这时尝试检查 j = next[next[4] - 1] = next[1] = 1 位置 s[j] = s[1] = 'c' = s[i + 1]，匹配成功，next[5] = j + 1 = 1 + 1 = 2

最后贴一段代码

impl Solution {
    pub fn longest_prefix(s: String) -> String {
        let cs: Vec<char> = s.chars().collect();
        let mut next = vec![0; s.len()];
        for i in 1..s.len() {
            // find match
            if cs[next[i-1]] == cs[i] {
                next[i] = next[i-1] + 1;
                continue;
            }

            if next[i-1] == 0 { continue; }

            // not find, decrease j to try match
            let mut j = next[next[i-1] - 1];
            while j >= 0 {
                if cs[j] == cs[i] {
                    next[i] = j + 1;    
                    break;
                }

                if j == 0 { break; }

                j = next[j-1];
            }
        }
        s[0..next[s.len() - 1]].to_string()
    }
}