算法 KMP next 数组构建的理解

lithium4010 · 2020年03月23日 · 4415 次阅读

研究这个的动机是因为 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()
    }
}
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请 注册新账号