Knuth–Morris–Pratt Algorithm (KMP Algorithm)

Definition

Definition

The Knuth–Morris–Pratt (KMP) Algorithm is a string searching algorithm that efficiently finds occurrences of a pattern within a text. It does so by utilizing information from previously matched characters to avoid unnecessary comparisons

Explanation

The KMP Algorithm works by precomputing a partial match table, also known as the "failure function" or "prefix function," for the pattern. This table enables the algorithm to determine the maximum length of a proper suffix of the pattern that matches a prefix of the pattern. During the matching process, the algorithm utilizes this information to efficiently skip unnecessary comparisons

Guidance

• Construct the partial match table for the pattern
• Initialize two pointers: one for the text (i) and one for the pattern (j) at the beginning of their respective strings
• Iterate through the text while the text pointer is less than its length
  • Compare characters at the text and pattern pointers
  • If the characters match, increment both pointers
  • If the characters don't match and the pattern pointer is not at the beginning, update the pattern pointer using information from the partial match table
  • If the characters don't match and the pattern pointer is at the beginning, move only the text pointer forward
  • Repeat steps until a match is found or the end of the text is reached

Tips

• utilize the partial match table to efficiently determine the next comparison position in the pattern
• avoid unnecessary backtracking by utilizing the information from the partial match table

Practice

Practice

computePrefixFunction(pattern):
  m = length of pattern
  prefixFunction[m]
  prefixFunction[0] = 0
  k = 0
  for q from 2 to m:
    while k > 0 and pattern[k+1] ≠ pattern[q]:
      k = prefixFunction[k]
    if pattern[k+1] == pattern[q]:
      k = k + 1
    prefixFunction[q] = k
  return prefixFunction

searchKMP(text, pattern):
  n = length of text
  m = length of pattern
  prefixFunction = computePrefixFunction(pattern)
  q = 0
  for i from 1 to n:
    while q > 0 and pattern[q+1] ≠ text[i]:
      q = prefixFunction[q]
    if pattern[q+1] == text[i]:
      q = q + 1
    if q == m:
      print "Pattern occurs with shift" i - m
      q = prefixFunction[q]

Solution

package main

func buildTable(pattern string) []int {
    table := make([]int, len(pattern))
    table[0] = 0
    prefix := 0

    for i := 1; i < len(pattern); i++ {
        for prefix > 0 && pattern[i] != pattern[prefix] {
            prefix = table[prefix-1]
        }
        if pattern[i] == pattern[prefix] {
            prefix++
        }
        table[i] = prefix
    }

    return table
}

func kmpSearch(text string, pattern string) []int {
    table := buildTable(pattern)
    matches := make([]int, 0)

    j := 0
    for i := 0; i < len(text); i++ {
        for j > 0 && text[i] != pattern[j] {
            j = table[j-1]
        }
        if text[i] == pattern[j] {
            j++
        }
        if j == len(pattern) {
            matches = append(matches, i-len(pattern)+1)
            j = table[j-1]
        }
    }

    return matches
}

import java.util.ArrayList;
import java.util.List;

public class KMP {

  public static int[] buildTable(String pattern) {
    int[] table = new int[pattern.length()];
    int prefix = 0;

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

    return table;
  }

  public static List<Integer> kmpSearch(String text, String pattern) {
    int[] table = buildTable(pattern);
    List<Integer> matches = new ArrayList<>();
    int j = 0;

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

    return matches;
  }
}

function buildTable(pattern) {
  const table = new Array(pattern.length).fill(0);
  let prefix = 0;

  for (let i = 1; i < pattern.length; i++) {
    while (prefix > 0 && pattern[i] !== pattern[prefix]) {
      prefix = table[prefix - 1];
    }
    if (pattern[i] === pattern[prefix]) {
      prefix++;
    }
    table[i] = prefix;
  }

  return table;
}

function kmpSearch(text, pattern) {
  const table = buildTable(pattern);
  const matches = [];
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = table[j - 1];
    }
    if (text[i] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      matches.push(i - pattern.length + 1);
      j = table[j - 1];
    }
  }

  return matches;
}

fun buildTable(pattern: String): IntArray {
    val table = IntArray(pattern.length)
    var prefix = 0

    for (i in 1 until pattern.length) {
        while (prefix > 0 && pattern[i] != pattern[prefix]) {
            prefix = table[prefix - 1]
        }
        if (pattern[i] == pattern[prefix]) {
            prefix++
        }
        table[i] = prefix
    }

    return table
}

fun kmpSearch(text: String, pattern: String): List<Int> {
    val table = buildTable(pattern)
    val matches = mutableListOf<Int>()
    var j = 0

    for (i in text.indices) {
        while (j > 0 && text[i] != pattern[j]) {
            j = table[j - 1]
        }
        if (text[i] == pattern[j]) {
            j++
        }
        if (j == pattern.length) {
            matches.add(i - pattern.length + 1)
            j = table[j - 1]
        }
    }

    return matches
}

def build_table(pattern):
    table = [0] * len(pattern)
    prefix = 0

    for i in range(1, len(pattern)):
        while prefix > 0 and pattern[i] != pattern[prefix]:
            prefix = table[prefix - 1]
        if pattern[i] == pattern[prefix]:
            prefix += 1
        table[i] = prefix

    return table

def kmp_search(text, pattern):
    table = build_table(pattern)
    matches = []
    j = 0

    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = table[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - len(pattern) + 1)
            j = table[j - 1]

    return matches

fn build_table(pattern: &str) -> Vec<usize> {
    let mut table = vec![0; pattern.len()];
    let mut prefix = 0;

    for (i, c) in pattern.chars().enumerate().skip(1) {
        while prefix > 0 && c != pattern.chars().nth(prefix).unwrap() {
            prefix = table[prefix - 1];
        }
        if c == pattern.chars().nth(prefix).unwrap() {
            prefix += 1;
        }
        table[i] = prefix;
    }

    table
}

fn kmp_search(text: &str, pattern: &str) -> Vec<usize> {
    let table = build_table(pattern);
    let mut matches = vec![];
    let mut j = 0;

    for (i, c) in text.chars().enumerate() {
        while j > 0 && c != pattern.chars().nth(j).unwrap() {
            j = table[j - 1];
        }
        if c == pattern.chars().nth(j).unwrap() {
            j += 1;
        }
        if j == pattern.len() {
            matches.push(i - pattern.len() + 1);
            j = table[j - 1];
        }
    }

    matches
}

function buildTable(pattern: string): number[] {
  const table: number[] = new Array(pattern.length).fill(0);
  let prefix = 0;

  for (let i = 1; i < pattern.length; i++) {
    while (prefix > 0 && pattern[i] !== pattern[prefix]) {
      prefix = table[prefix - 1];
    }
    if (pattern[i] === pattern[prefix]) {
      prefix++;
    }
    table[i] = prefix;
  }

  return table;
}

function kmpSearch(text: string, pattern: string): number[] {
  const table = buildTable(pattern);
  const matches: number[] = [];
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = table[j - 1];
    }
    if (text[i] === pattern[j]) {
      j++;
    }
    if (j === pattern.length) {
      matches.push(i - pattern.length + 1);
      j = table[j - 1];
    }
  }

  return matches;
}