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)) {

Try this exercise. Is this statement true or false?

The Knuth-Morris-Pratt (KMP) algorithm is an example of a string matching algorithm.

Press true if you believe the statement is correct, or false otherwise.

Suffix Arrays

A suffix array is a sorted array of all the suffixes of a given string. It is a powerful data structure used in string processing and pattern searching algorithms.

The suffix array can be constructed by comparing the suffixes of a string based on their lexicographic order. Once the suffix array is constructed, it can be used to efficiently solve various string-related problems such as substring search, longest common prefix, pattern matching, and more.

Here is an example implementation of building a suffix array in Java:

TEXT/X-JAVA

1import java.util.Arrays;
2
3class Suffix {
4
5  private int index;
6  private String suffix;
7
8  public Suffix(int index, String suffix) {
9    this.index = index;
10    this.suffix = suffix;
11  }
12
13  public int getIndex() {
14    return index;
15  }
16
17  public String getSuffix() {
18    return suffix;
19  }
20}
21
22public class SuffixArray {
23
24  public int[] buildSuffixArray(String text) {
25    int n = text.length();
26    Suffix[] suffixes = new Suffix[n];
27
28    for (int i = 0; i < n; i++) {
29      suffixes[i] = new Suffix(i, text.substring(i));
30    }
31
32    Arrays.sort(suffixes);
33
34    int[] suffixArray = new int[n];
35    for (int i = 0; i < n; i++) {
36      suffixArray[i] = suffixes[i].getIndex();
37    }
38
39    return suffixArray;
40  }
41
42  public static void main(String[] args) {
43    SuffixArray suffixArray = new SuffixArray();
44
45    String text = "banana";
46    int[] suffixes = suffixArray.buildSuffixArray(text);
47
48    System.out.println("Suffix Array:");
49    for (int suffix : suffixes) {
50      System.out.println(suffix);
51    }
52  }
53}

xxxxxxxxxx
}
 
class SuffixArray {
​
  public int[] buildSuffixArray(String text) {
    int n = text.length();
    Suffix[] suffixes = new Suffix[n];
​
    for (int i = 0; i < n; i++) {
      suffixes[i] = new Suffix(i, text.substring(i));
    }
​
    Arrays.sort(suffixes);
​
    int[] suffixArray = new int[n];
    for (int i = 0; i < n; i++) {
      suffixArray[i] = suffixes[i].getIndex();
    }
​
    return suffixArray;
  }
​
  public static void main(String[] args) {
    SuffixArray suffixArray = new SuffixArray();
​
    String text = "banana";
    int[] suffixes = suffixArray.buildSuffixArray(text);
​
    System.out.println("Suffix Array:");
    for (int suffix : suffixes) {
      System.out.println(suffix);

Try this exercise. Click the correct answer from the options.

What is the purpose of constructing a suffix array?

Click the option that best answers the question.

To efficiently search for a substring in a given string
To sort a given string in lexicographic order
To count the number of occurrences of a character in a given string
To compress a given string by removing repeating characters

Tries

Tries, also known as prefix trees or digital trees, are tree-based data structures used for efficient string searching and manipulation. Tries excel at tasks like autocomplete suggestions, spell checking, and search suggestions.

A trie is a multi-way tree that stores keys, where each node represents a single character of a string. Unlike a binary search tree, each node in a trie can have multiple children, equal to the number of unique characters in the string alphabet. Each node also has a boolean flag to indicate if it marks the end of a word.

Here's an example implementation of a Trie in Java:

TEXT/X-JAVA

1import java.util.HashMap;
2import java.util.Map;
3
4class TrieNode {
5    private Map<Character, TrieNode> children;
6    private boolean isEndOfWord;
7
8    public TrieNode() {
9        children = new HashMap<>();
10        isEndOfWord = false;
11    }
12
13    public boolean isEndOfWord() {
14        return isEndOfWord;
15    }
16
17    public void setEndOfWord(boolean endOfWord) {
18        isEndOfWord = endOfWord;
19    }
20
21    public TrieNode getChild(char ch) {
22        return children.get(ch);
23    }
24
25    public void addChild(char ch) {
26        children.put(ch, new TrieNode());
27    }
28}
29
30public class Trie {
31    private TrieNode root;
32
33    public Trie() {
34        root = new TrieNode();
35    }
36
37    public void insert(String word) {
38        TrieNode current = root;
39        for (int i = 0; i < word.length(); i++) {
40            char ch = word.charAt(i);
41            TrieNode node = current.getChild(ch);
42            if (node == null) {
43                current.addChild(ch);
44                node = current.getChild(ch);
45            }
46            current = node;
47        }
48        current.setEndOfWord(true);
49    }
50
51    public boolean search(String word) {
52        TrieNode current = root;
53        for (int i = 0; i < word.length(); i++) {
54            char ch = word.charAt(i);
55            TrieNode node = current.getChild(ch);
56            if (node == null) {
57                return false;
58            }
59            current = node;
60        }
61        return current.isEndOfWord();
62    }
63
64    public boolean startsWith(String prefix) {
65        TrieNode current = root;
66        for (int i = 0; i < prefix.length(); i++) {
67            char ch = prefix.charAt(i);
68            TrieNode node = current.getChild(ch);
69            if (node == null) {
70                return false;
71            }
72            current = node;
73        }
74        return true;
75    }
76
77    public static void main(String[] args) {
78        Trie trie = new Trie();
79        trie.insert("apple");
80        trie.insert("banana");
81
82        System.out.println(trie.search("apple")); // true
83        System.out.println(trie.search("banana")); // true
84        System.out.println(trie.search("orange")); // false
85
86        System.out.println(trie.startsWith("app")); // true
87        System.out.println(trie.startsWith("ban")); // true
88        System.out.println(trie.startsWith("ora")); // false
89    }
90}

xxxxxxxxxx
}
 
import java.util.HashMap;
import java.util.Map;
​
class TrieNode {
    private Map<Character, TrieNode> children;
    private boolean isEndOfWord;
​
    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
​
    public boolean isEndOfWord() {
        return isEndOfWord;
    }
​
    public void setEndOfWord(boolean endOfWord) {
        isEndOfWord = endOfWord;
    }
​
    public TrieNode getChild(char ch) {
        return children.get(ch);
    }
​
    public void addChild(char ch) {
        children.put(ch, new TrieNode());
    }
}
​

Are you sure you're getting this? Is this statement true or false?

A trie is a binary search tree used for efficient string searching and manipulation.

Press true if you believe the statement is correct, or false otherwise.

Putting It Together

Congratulations on completing the String Algorithms tutorial! You have learned about various string manipulation algorithms, including checking for palindromes, anagrams, finding the longest common substring, and reversing a string.

By understanding these algorithms, you are equipped with the fundamental knowledge to tackle more complex string manipulation tasks. String algorithms play a crucial role in many domains, including text processing, natural language processing, and data analysis.

Remember, string manipulation is not just about the mechanics of dealing with text; it requires thinking algorithmically and applying logical thought processes. The algorithms you have learned here will serve as building blocks for solving more significant problems in your coding journey.

Now that you have a solid foundation in string algorithms, it's time to explore other advanced data structures and algorithms. Continuously challenge yourself and practice implementing these concepts in real-world scenarios. Enjoy your coding journey!

xxxxxxxxxx
 
class Main {
  public static void main(String[] args) {
    // Replace with your Java logic here
    System.out.println("Thank you for completing the String Algorithms tutorial!");
  }
}

Let's test your knowledge. Click the correct answer from the options.

What is an important skill required for solving string manipulation problems?

Click the option that best answers the question.

Understanding the properties and operations of strings
Knowing the syntax of popular programming languages
Memorizing all the string manipulation algorithms
Having extensive experience in database management

Generating complete for this lesson!

String Matching Algorithms

Knuth-Morris-Pratt Algorithm

Try this exercise. Is this statement true or false?

Suffix Arrays

Try this exercise. Click the correct answer from the options.

Click the option that best answers the question.

Tries

Are you sure you're getting this? Is this statement true or false?

Putting It Together

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Programming Categories

Popular Lessons