AlgoDaily - String Algorithms

Home > Advanced data structures and algorithms > Advanced data structures and algorithms > String Algorithms

String Matching Algorithms

String matching algorithms are algorithms designed to find a pattern in a given string. These algorithms are used in various applications such as text editing, DNA sequencing, and data compression. Two well-known string matching algorithms are the Knuth-Morris-Pratt (KMP) algorithm and the Boyer-Moore algorithm.

Knuth-Morris-Pratt Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is a string matching algorithm that avoids unnecessary comparisons by utilizing information about the pattern being searched. It preprocesses the pattern to create a “failure function,” which helps skip comparisons when a mismatch occurs. This leads to a more efficient search process.

Here's an example implementation of the KMP algorithm in Java:

TEXT/X-JAVA

1// Knuth-Morris-Pratt Algorithm
2
3public class KnuthMorrisPratt {
4
5  private int[] computePrefix(String pattern) {
6    int[] prefix = new int[pattern.length()];
7    int j = 0;
8    for (int i = 1; i < pattern.length(); i++) {
9      if (pattern.charAt(i) == pattern.charAt(j)) {
10        prefix[i] = j + 1;
11        j++;
12      } else if (j > 0){
13        j = prefix[j - 1];
14        i--;
15      }
16    }
17    return prefix;
18  }
19
20  public boolean search(String text, String pattern) {
21    int[] prefix = computePrefix(pattern);
22    int j = 0;
23    for (int i = 0; i < text.length(); i++) {
24      if (text.charAt(i) == pattern.charAt(j)) {
25        j++;
26        if (j == pattern.length()) {
27          return true;
28        }
29      } else if (j > 0) {
30        j = prefix[j - 1];
31        i--;
32      }
33    }
34    return false;
35  }
36
37  public static void main(String[] args) {
38    KnuthMorrisPratt kmp = new KnuthMorrisPratt();
39
40    String text = "ABABDABACDABABCABAB";
41    String pattern = "ABABCABAB";
42
43    boolean found = kmp.search(text, pattern);
44    System.out.println(found); // true
45  }
46}

xxxxxxxxxx
}
 
// Knuth-Morris-Pratt Algorithm
​
public class KnuthMorrisPratt {
​
  private int[] computePrefix(String pattern) {
    int[] prefix = new int[pattern.length()];
    int j = 0;
    for (int i = 1; i < pattern.length(); i++) {
      if (pattern.charAt(i) == pattern.charAt(j)) {
        prefix[i] = j + 1;
        j++;
      } else if (j > 0){
        j = prefix[j - 1];
        i--;
      }
    }
    return prefix;
  }
​
  public boolean search(String text, String pattern) {
    int[] prefix = computePrefix(pattern);
    int j = 0;
    for (int i = 0; i < text.length(); i++) {
      if (text.charAt(i) == pattern.charAt(j)) {
        j++;
        if (j == pattern.length()) {
          return true;
        }
      } else if (j > 0) {

xxxxxxxxxx
}
 
// Boyer-Moore Algorithm
​
public class BoyerMoore {
​
  private int[] computeBadCharacterTable(String pattern) {
    int[] badCharacter = new int[256];
    for (int i = 0; i < pattern.length(); i++) {
      int ascii = pattern.charAt(i);
      badCharacter[ascii] = i;
    }
    return badCharacter;
  }
  
  private int[] computeSuffixTable(String pattern) {
    int m = pattern.length();
    int[] suffix = new int[m];
    int f = 0;
    int g = m - 1;
​
    suffix[m - 1] = m;
    for (int i = m - 2; i >= 0; i--) {
      if (i > g && suffix[i + m - 1 - f] < i - g) {
          suffix[i] = suffix[i + m - 1 - f];
      } else {
          if (i < g) {
              g = i;
          }
          f = i;
          while (g >= 0 && pattern.charAt(g) == pattern.charAt(g + m - 1 - f)) {

String Matching Algorithms

Knuth-Morris-Pratt Algorithm

Programming Categories

Popular Lessons