KMP algorithm

Introduction

KMP演算法，給定字串s和字串t，可以快速地找出字串t是否為字串s的子字串

Time complexity: O(n)

Prefix function(Failure function)

陣列 f[i]: 代表在s[0:i]中次長的prefix長度，且同時也是suffix。

• 最長的prefix且同時也是suffix長度為s[0:i]本身

• Example:

  • "abcabcd": [0, 1, 0, 1, 2, 2, 3]

Naive algorithm

vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> f(n);
    for(int i=0; i<n; i++) {
        for(int k=0; k<=i; k++) {
            if (s.substr(0, k) == s.substr(i - k +1, k)) 
                f[i] = k;
        }
    }
}

Optimized algorithm

• Optimization 1: f[i+1]的值 最大為f[i] + 1
  • 代表從index i到i+1，最多只會增加1。
  • 利用此特性可以優化演算法複雜度到O(n^2)

vector<int> prefix_function_optimize_1(string s) {
    int n = s.size();
    vector<int> f(n);

    int k = 1; // current step + 1
    
    for(int i=0; i<n; i++) {

        while (s.substr(0, k) != s.substr(i - k +1, k)) {
            k--;
        }
        f[i] = k;
        k++; 
    }
}

• Optimization 2: 當要計算f[i+1]時:
  • 假如 s[i+1] == s[f[i]] (從0開始的第f[i]個字母)
    • 代表 f[i+1] = f[i] + 1
  • 若不一樣，則需要快速找到f[i]的次長子字串去做比對
    • 觀察後可以發現次長子字串 len = f[f[i] - 1]
      • j = f[i] - 1: 從0開始數的第f[i] - 1個index
      • f[j]: 在 s[0:j]中符合條件的次長子自串。
        • 因為之前計算過了，所以可以快速取得

vector<int> prefix_function_optimize_2(string s) {
    int n = s.size();

    vector<int> f(n);
    for(int i=1; i<n; i++) {
        int j = f[i-1];
        while(j > 0 && s[i] != s[j]) {
            j = f[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        f[i] = j;
    }
    return f;
}

int kmp(string pattern, string text) {
    // find if pattern in text
    auto f = prefix_function_optimize_2(pattern);

    // try to find the prefix of text again.
    int pi = 0;
    vector<int> pos;

    for(int ti = 0; ti < n; ti++) {
        int pi = f[pi - 1];
        while(pi > 0 and pattern[pi] != text[ti]) {
            pi = f[pi - 1];
        }
        if (pattern[j] == text[ti]) {
            pi++;
        }
        if (pi == pattern.size()) {
            // find
            pos.push_back(ti - m + 1);
            pi = f[pi - 1];
        }
    }
    return pos;
}