【算法與資料結構】字元串模式比對 KMP 算法

語義

在一個很長的字元串 T 中，查找是否存在子字元串 P。例如搜尋引擎收錄的大量網站資料，當使用者輸入關鍵字後，就會在這些資料中進行比對，并傳回合适的網站。

語義：假定字元串長度為 j，則所有字元串都在

[0, j)

這樣的集合中。

傳回首次比對的字元的位置。注意這裡調用方需要判斷位置是否正确，例如對于長度為 i 的字元串，要查找是否有長度為 j 的字元串，如果傳回值在

[0, i - j)

則為正确比對到資料，否則就是失敗。

暴力比對 brute force

每次用 T 的一個字元比對 pattern 的所有字元，全部比對成功則傳回首字元下标，否則 T 前進一個字元，繼續比對：

#include <stdio.h>
#include <string.h>

int match(char *str, char *pattern) {
    int i = 0, j = 0;
    int sLen = strlen(str);
    int pLen = strlen(pattern);
    if (sLen < 1 || pLen < 1) {
        return -1;
    }
    while (i < sLen && j < pLen) {
        if (str[i] == pattern[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    return i - j;
}

int main(void) {
    char *str = "sfeiwojdsljfldshgew";
    printf("str length is:%ld\n", strlen(str));
    char *pattern[] = {
        "",
        "a",
        "abc",
        "woj",
        "wojdsljflda"
    };
    int i, ret;
    int len = sizeof(pattern) / sizeof(char *);
    for (i = 0; i < len; i++) {
        ret = match(str, pattern[i]);
        printf("ret is:%4d, correct range is:%ld, raw is:%s\n", ret, strlen(str) - strlen(pattern[i]), pattern[i]);
    }

    return 0;
}
           

KMP

最長公共前字尾

這裡通常取的是真字首（不包含最後一個字元）和真字尾（不包含第一個字元）。長度相同的前字尾就是公共前字尾。

例如：

• a

  : ``，最長公共前字尾長度為 0

• aa

  :

  a

  ，最長公共前字尾長度為 1

• ab

  : ``，最長公共前字尾長度為 0

• aaa

  :

  aa

  ，最長公共前字尾長度為 2

• abab

  :

  ab

  ，最長公共前字尾長度為 2

字首表

任意的字元串 P，對其每個字元前面的子字元串找最長公共前字尾，得到的這個數組就是字首表。

例如，對于字元串

ababc

：

• a

  : ``，真字首為空字元串，其最長公共前字尾長度記為 -1

• ab

  : ``，真字首為

  a

  ，其最長公共前字尾長度為 0

• aba

  :

  a

  ，真字首為

  ab

  ，其最長公共前字尾長度為 0（最長字首

  a

  和最長字尾

  a

  不比對）

• abab

  :

  ab

  ，真字首為

  aba

  ，其最長公共前字尾長度為 1

• ababc

  : ``，真字首為

  abab

  ，其最長公共前字尾長度為 2

最終的字首表數組：[-1, 0, 0, 1, 2]

KMP 算法

package main

import "fmt"

func kmp(target string, pattern string) []int {
    var ret []int
    length := len(pattern)
    prefixTable := buildPrefixTable(pattern)
    i := 0
    k := 0
    for {
        if i + length > len(target) {
            break
        }
        if target[i + k] == pattern[k] {
            k += 1
            if k == length {
                ret = append(ret, i)
                k = 0
                i += 1
                continue
            }
        } else {
            diff := k - prefixTable[k]
            i += diff
            if k > 0 {
                k -= diff
            }
        }
    }
    return ret
}

func buildPrefixTable(str string) []int {
    ret := []int{-1}
    for i := range str {
        if i == 0 {
            continue
        }
        pre := str[:i]
        j := len(pre) - 1
        for j > 0 {
            if pre[:j] == pre[len(pre) - j:] {
                ret = append(ret, j)
                break
            }
            j = j - 1
        }
        if len(ret) < len(pre) + 1 {
            ret = append(ret, 0)
        }
    }
    return ret
}

func main() {
    ret := kmp("abacaca", "aca")
    fmt.Println(ret)
}