LOGI

KMP 算法

在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称为 KMP 算法）可在一个字符串 S 内查找一个词 W 的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前匹配的字符。

这个算法由高德纳和沃恩·普拉特在 1974 年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于 1977 年联合发表。

Exhaustive Method

// 穷举法，时间复杂度：O(mn)，空间复杂度：O(1)
func bruteForce(s, p string) int {
    n := len(s)
    m := len(p)

    if n < m {
        return -1
    }

    for i := 0; i <= n-m; i++ {
        j := 0
        for ; j < m; j++ {
            if s[i+j] != p[j] {
                break
            }
        }
        if j == m {
            return i
        }
    }

    return -1
}

Longest Common Subsequence Model

// 穷举计算模式串各子串最长公共前后缀（真子串）长度
// 时间复杂度：O(n^2)，空间复杂度：O(1)
func buildNextForce(p string) []int {
    n := len(p)
    next := make([]int, n)

    // 当前串长：i+1
    for i := 0; i < n; i++ {
        // 公共前后缀长度：j，范围：[0, i+1)，逆序遍历求最长
        for j := i; j >= 0; j-- {
            // 前缀头下标：0，后缀尾下标：i
            // a b c a b
            // 0 1 2 3 4
            //       3 4
            // 3 = 5 - 2, 后缀头下标：i+1-j
            s := i + 1 - j
            k := 0
            for ; k < j; k++ {
                if p[k] != p[s+k] {
                    break
                }
            }
            if k == j {
                next[i] = j
                break
            }
        }
    }

    return next
}

// 递推计算模式串各子串最长公共前后缀长度
// 时间复杂度：O(n)，空间复杂度：O(1)
func buildNext(p string) []int {
    n := len(p)
    next := make([]int, n)

    // next[i] 是 p[0, i] 的最长公共前后缀长度
    // a b c a b c
    // 0 1 2 3 4 5
    next[0] = 0
    j := next[0] // j 是 next[i-1]
    for i := 1; i < n; {
        // p[i] 是后缀待比较字符
        // p[j] 是前缀待比较字符
        if p[i] == p[j] {
            next[i] = j + 1
            i++
            j = next[i-1] // 为下次循环更新
        } else if j > 0 {
            j = next[j-1]
        } else { // j 此时为 0
            next[i] = 0
            i++
        }
    }

    return next
}

KMP Search

// 根据模式串各子串最长公共前后缀长度尽可能减少回退
// 时间复杂度：O(n+m)，空间复杂度：O(m)
func kmp(s, p string) int {
    n := len(s)
    m := len(p)

    if n < m {
        return -1
    }

    next := buildNext(p)
    j := 0
    for i := 0; i < n; {
        if s[i] == p[j] {
            i++
            j++
        } else if j > 0 {
            j = next[j-1]
        } else {
            i++
        }

        if j == m {
            // a b c a b
            // 0 1 2 3 4 i
            //       0 1 j
            // 3 = 5 - 2
            return i - j
        }
    }

    return -1
}

Dynamic Programming Method

public class KMP {
    private int[][] dp;
    private String pat;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 构建状态转移图（稍改的更紧凑了）
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++)
                dp[j][c] = dp[X][c];
            dp[j][pat.charAt(j)] = j + 1;
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {
        int M = pat.length();
        int N = txt.length();
        // pat 的初始态为 0
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 计算 pat 的下一个状态
            j = dp[j][txt.charAt(i)];
            // 到达终止态，返回结果
            if (j == M) return i - M + 1;
        }
        // 没到达终止态，匹配失败
        return -1;
    }
}

Complete Code

[collapse title="Golang"]

package main

import (
    "fmt"
)

// 穷举法，时间复杂度：O(mn)，空间复杂度：O(1)
func bruteForce(s, p string) int {
    n := len(s)
    m := len(p)

    if n < m {
        return -1
    }

    for i := 0; i <= n-m; i++ {
        j := 0
        for ; j < m; j++ {
            if s[i+j] != p[j] {
                break
            }
        }
        if j == m {
            return i
        }
    }

    return -1
}

// 穷举计算模式串各子串最长公共前后缀（真子串）长度
// 时间复杂度：O(n^2)，空间复杂度：O(1)
func buildNextForce(p string) []int {
    n := len(p)
    next := make([]int, n)

    // 当前串长：i+1
    for i := 0; i < n; i++ {
        // 公共前后缀长度：j，范围：[0, i+1)，逆序遍历求最长
        for j := i; j >= 0; j-- {
            // 前缀头下标：0，后缀尾下标：i
            // a b c a b
            // 0 1 2 3 4
            //       3 4
            // 3 = 5 - 2, 后缀头下标：i+1-j
            s := i + 1 - j
            k := 0
            for ; k < j; k++ {
                if p[k] != p[s+k] {
                    break
                }
            }
            if k == j {
                next[i] = j
                break
            }
        }
    }

    return next
}

// 递推计算模式串各子串最长公共前后缀长度
// 时间复杂度：O(n)，空间复杂度：O(1)
func buildNext(p string) []int {
    n := len(p)
    next := make([]int, n)

    // next[i] 是 p[0, i] 的最长公共前后缀长度
    // a b c a b c
    // 0 1 2 3 4 5
    next[0] = 0
    j := next[0] // j 是 next[i-1]
    for i := 1; i < n; {
        // p[i] 是后缀待比较字符
        // p[j] 是前缀待比较字符
        if p[i] == p[j] {
            next[i] = j + 1
            i++
            j = next[i-1] // 为下次循环更新
        } else if j > 0 {
            j = next[j-1]
        } else { // j 此时为 0
            next[i] = 0
            i++
        }
    }

    return next
}

// 根据模式串各子串最长公共前后缀长度尽可能减少回退
// 时间复杂度：O(n+m)，空间复杂度：O(m)
func search(s, p string) int {
    n := len(s)
    m := len(p)

    if n < m {
        return -1
    }

    next := buildNext(p)
    j := 0
    for i := 0; i < n; {
        if s[i] == p[j] {
            i++
            j++
        } else if j > 0 {
            j = next[j-1]
        } else {
            i++
        }

        if j == m {
            // a b c a b
            // 0 1 2 3 4 i
            //       0 1 j
            // 3 = 5 - 2
            return i - j
        }
    }

    return -1
}

func main() {
    s := "ababaabaabac"
    p := "abaabac"

    fmt.Println(buildNextForce(p))
    fmt.Println(buildNext(p))
    fmt.Println(bruteForce(s, p))
    fmt.Println(search(s, p))

    /*
        Output:
        [0 0 1 1 2 3 0]
        [0 0 1 1 2 3 0]
        5
        5
    */
}

[/collapse]

[collapse title="Java"]

package com.logi.algorithm;

import java.util.Arrays;

public class Kmp {

    // 递推计算模式串各子串最长公共前后缀长度
    // 时间复杂度：O(n)，空间复杂度：O(1)
    private static int[] buildNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = 0;
        for (int i = 1; i < pattern.length(); i++) {
            int j = next[i - 1];
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j - 1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                next[i] = j + 1;
            } else {
                next[i] = 0;
            }
        }

        return next;
    }

    // 根据模式串各子串最长公共前后缀长度尽可能减少回退
    // 时间复杂度：O(n+m)，空间复杂度：O(m)
    public static int indexOf(String text, String pattern) {
        if (text.length() < pattern.length()) {
            return -1;
        }

        int[] next = buildNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }

        return j == pattern.length() ? i - j : -1;
    }

    public static void main(String[] args) {
        String text = "ababaabaabac";
        String pattern = "abaabac";
        int[] expectedNext = new int[] { 0, 0, 1, 1, 2, 3, 0 };
        int expectedIndex = 5;

        System.out.println(Arrays.equals(expectedNext, buildNext(pattern)));
        System.out.println(expectedIndex == indexOf(text, pattern));
    }
}

[/collapse]

References

  1. 如何更好地理解和掌握 KMP 算法?
  2. 动态规划之 KMP 字符串匹配算法
  3. 可能是最容易理解的 KMP 教程

当前页面是本站的「Google AMP」版。查看和发表评论请点击：完整版 »