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:

// 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) {
        j = prefix[j - 1];
        i--;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    KnuthMorrisPratt kmp = new KnuthMorrisPratt();

    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";

    boolean found = kmp.search(text, pattern);
    System.out.println(found); // true
  }
}

```java
// 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) {
        j = prefix[j - 1];
        i--;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    KnuthMorrisPratt kmp = new KnuthMorrisPratt();

    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";

    boolean found = kmp.search(text, pattern);
    System.out.println(found); // true
  }
}
```

```java
// 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)) {
              g--;
          }
          suffix[i] = f - g;
      }
    }
    return suffix;
  }
  
  public boolean search(String text, String pattern) {
    int[] badCharacter = computeBadCharacterTable(pattern);
    int[] suffix = computeSuffixTable(pattern);

    int n = text.length();
    int m = pattern.length();
    int i = m - 1;
    int j = m - 1;

    while (i < n) {
      if (text.charAt(i) == pattern.charAt(j)) {
        if (j == 0) {
          return true;
        }
        i--;
        j--;
      } else {
        int badChar = text.charAt(i);
        int badCharIndex = badCharacter[badChar];
        int shiftBy = j - badCharIndex;
        if (shiftBy < 1) {
          shiftBy = 1;
        }

        int suffixShift = suffix[j];
        if (suffixShift > shiftBy) {
          shiftBy = suffixShift;
        }

        i += shiftBy;
        j = m - 1;
      }
    }

    return false;
  }

  public static void main(String[] args) {
    BoyerMoore bm = new BoyerMoore();

    String text = "ABABDABACDABABCABAB";
    String pattern = "ABABCABAB";

    boolean found = bm.search(text, pattern);
    System.out.println(found); // true
  }
}
```

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

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:

import java.util.Arrays;

class Suffix {

  private int index;
  private String suffix;

  public Suffix(int index, String suffix) {
    this.index = index;
    this.suffix = suffix;
  }

  public int getIndex() {
    return index;
  }

  public String getSuffix() {
    return suffix;
  }
}

public 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);
    }
  }
}

```java
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);
    }
  }
}

```

What is the purpose of constructing a suffix array?

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:

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());
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                current.addChild(ch);
                node = current.getChild(ch);
            }
            current = node;
        }
        current.setEndOfWord(true);
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord();
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("banana");

        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("banana")); // true
        System.out.println(trie.search("orange")); // false

        System.out.println(trie.startsWith("app")); // true
        System.out.println(trie.startsWith("ban")); // true
        System.out.println(trie.startsWith("ora")); // false
    }
}

```java
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());
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                current.addChild(ch);
                node = current.getChild(ch);
            }
            current = node;
        }
        current.setEndOfWord(true);
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.isEndOfWord();
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            TrieNode node = current.getChild(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("banana");

        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("banana")); // true
        System.out.println(trie.search("orange")); // false

        System.out.println(trie.startsWith("app")); // true
        System.out.println(trie.startsWith("ban")); // true
        System.out.println(trie.startsWith("ora")); // false
    }
}
```

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

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!

```java
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!");
  }
}
```

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

Generating complete for this lesson!