KMP

Given an array pattern, failure_function(pattern) returns a failure function failure of pattern.

Given an array haystack, kmp_search(haystack, pattern, failure) returns a result of searching pattern in haystack, given that failure is a proper failure function of pattern. Denoting the returned array as result and the length of pattern as n, if result[i + n] == n, then result[i..n] == pattern.

The API looks like this, as the failure function itself is needed in many algorithm problems, rather than directly using KMP for a string searching.

Example

fn main() {
let pattern = b"ABCDABC";
let targets = ["ABDABCDABCE", "ABCDABCDABCD", "ABBCCABCDABDABCDABC"].map(|b| b.as_bytes());

let failure = failure_function(pattern);
for &t in &targets {
    let result = kmp_search(t, pattern, &failure);
    println!("{:?}", result);
    for i in 0..result.len() - pattern.len() {
        if result[i + pattern.len()] == pattern.len() {
            print!("{} ", i);
        }
    }
    println!();
}
}

/// Returns a failure function of `pattern`.
fn failure_function<T: PartialEq>(pattern: &[T]) -> Vec<usize> {
    let n = pattern.len();
    let mut c = vec![0, 0];
    let mut x;
    for i in 1..n {
        x = c[i];
        loop {
            if pattern[i] == pattern[x] {
                c.push(x + 1);
                break;
            }
            if x == 0 {
                c.push(0);
                break;
            }
            x = c[x];
        }
    }
    c
}

/// Returns a result of KMP search.
/// For `n = pattern.len()`, if `result[i] == n`, then `haystack[i-n..i] == pattern`.
fn kmp_search<T: PartialEq>(haystack: &[T], pattern: &[T], failure: &[usize]) -> Vec<usize> {
    let m = haystack.len();
    let mut d = vec![0];
    let mut x;
    for i in 0..m {
        x = d[i];
        if x == pattern.len() {
            x = failure[x];
        }
        loop {
            if haystack[i] == pattern[x] {
                d.push(x + 1);
                break;
            }
            if x == 0 {
                d.push(0);
                break;
            }
            x = failure[x];
        }
    }
    d
}

Code

/// Returns a failure function of `pattern`.
fn failure_function<T: PartialEq>(pattern: &[T]) -> Vec<usize> {
    let n = pattern.len();
    let mut c = vec![0, 0];
    let mut x;
    for i in 1..n {
        x = c[i];
        loop {
            if pattern[i] == pattern[x] {
                c.push(x + 1);
                break;
            }
            if x == 0 {
                c.push(0);
                break;
            }
            x = c[x];
        }
    }
    c
}

/// Returns a result of KMP search.
/// For `n = pattern.len()`, if `result[i] == n`, then `haystack[i-n..i] == pattern`.
fn kmp_search<T: PartialEq>(haystack: &[T], pattern: &[T], failure: &[usize]) -> Vec<usize> {
    let m = haystack.len();
    let mut d = vec![0];
    let mut x;
    for i in 0..m {
        x = d[i];
        if x == pattern.len() {
            x = failure[x];
        }
        loop {
            if haystack[i] == pattern[x] {
                d.push(x + 1);
                break;
            }
            if x == 0 {
                d.push(0);
                break;
            }
            x = failure[x];
        }
    }
    d
}

Last modified on 231008.