String Algorithms in Competitive Programming (Java)

Introduction to String Algorithms

Strings are fundamental data structures in computer science, and efficient string algorithms are crucial in competitive programming. Problems involving string matching, pattern searching, manipulation, and analysis are common. Mastering these algorithms can significantly improve your ability to solve a wide range of problems efficiently.

Common String Algorithms and Techniques

1. String Matching

String matching involves finding occurrences of a given pattern string within a larger text string. Several algorithms exist, each with its own trade-offs in terms of time and space complexity.

a. Brute Force String Matching

The simplest approach is brute force. It involves sliding the pattern string along the text string and comparing characters at each position.

Java Implementation:

 public class BruteForceStringMatching {

    public static int bruteForceSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // Mismatch found
                }
            }
            if (j == m) {
                return i; // Pattern found at index i
            }
        }
        return -1; // Pattern not found
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int index = bruteForceSearch(text, pattern);

        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found.");
        }
    }
} 

Time Complexity: O(n*m) where n is the length of the text and m is the length of the pattern. In the worst case, this is very inefficient.

b. Knuth-Morris-Pratt (KMP) Algorithm

KMP is a more efficient algorithm that preprocesses the pattern to create a "longest proper prefix suffix" (LPS) array. This array helps avoid unnecessary comparisons by utilizing information about previously matched characters.

Java Implementation:

 public class KMPStringMatching {

    public static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0; // Length of the previous longest prefix suffix
        int i = 1;

        lps[0] = 0; // lps[0] is always 0

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1]; // This is tricky. Consider "AAACAAAA"
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        int[] lps = computeLPSArray(pattern);

        int i = 0; // Index for text[]
        int j = 0; // Index for pattern[]

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                return i - j; // Pattern found at index i-j
                //j = lps[j - 1];  // Uncomment to find all occurrences
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // Pattern not found
    }


    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int index = kmpSearch(text, pattern);

        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found.");
        }
    }
} 

Time Complexity: O(n + m) where n is the length of the text and m is the length of the pattern. This is a significant improvement over brute force.

c. Boyer-Moore Algorithm

Boyer-Moore is another efficient string matching algorithm that uses two heuristics: the "bad character heuristic" and the "good suffix heuristic." It often performs better than KMP in practice, especially for longer patterns.

Java Implementation: (Illustrative example, can be complex for full implementation)

 // Partial example illustrating the bad character heuristic
public class BoyerMooreExample {

    public static int boyerMooreSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        // Bad character heuristic - Create a table of last occurrences
        int[] badChar = new int[256]; // Assuming ASCII characters
        for (int i = 0; i < 256; i++) {
            badChar[i] = -1; // Initialize to -1 (not found)
        }
        for (int i = 0; i < m; i++) {
            badChar[(int) pattern.charAt(i)] = i; // Store last occurrence index
        }

        int s = 0; // s is shift of the pattern with respect to text
        while (s <= (n - m)) {
            int j = m - 1;

            // Keep reducing index j of pattern while characters of pattern and text are matching
            while (j >= 0 && pattern.charAt(j) == text.charAt(s + j)) {
                j--;
            }

            // If the pattern is present at the current shift, then index j will become -1
            if (j < 0) {
                System.out.println("Pattern occurs at shift = " + s);
                return s; // Return first occurence

                //s += (s + m < n) ? m - badChar[text.charAt(s + m)] : 1; // Use for ALL occurrences
            } else {

                // Shift the pattern so that the bad character in text aligns with the last
                // occurrence of it in pattern. The max function is used to make sure that we get a positive shift.
                s += Math.max(1, j - badChar[text.charAt(s + j)]);
            }
        }
        return -1; // Pattern not found
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int index = boyerMooreSearch(text, pattern);

        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found.");
        }
    }
} 

Time Complexity: Best case O(n/m), Average case O(n), Worst case O(n*m) (rare with good implementations). The preprocessing takes O(m + character set size).

2. Pattern Searching

Pattern searching often involves more complex patterns than simple strings, such as regular expressions. While Java's built-in `Pattern` and `Matcher` classes are powerful, specialized algorithms can be more efficient in specific cases.

a. Regular Expressions (using `Pattern` and `Matcher` in Java)

Java provides robust support for regular expressions through the `java.util.regex` package.

Java Implementation:

 import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RegexPatternSearching {

    public static void main(String[] args) {
        String text = "The quick brown fox jumps over the lazy dog. The fox is quick.";
        String patternString = "fox"; // Simple pattern

        Pattern pattern = Pattern.compile(patternString);
        Matcher matcher = pattern.matcher(text);

        while (matcher.find()) {
            System.out.println("Found match at index: " + matcher.start());
        }
    }
} 

Time Complexity: Difficult to precisely state; depends heavily on the complexity of the regular expression and the matching engine's implementation. Can range from near-linear to exponential in pathological cases. Avoid complex backtracking patterns for performance-critical sections.

b. Trie Data Structure for Pattern Searching

A Trie (also known as a prefix tree) is a tree-like data structure used for efficient retrieval of a set of strings. It's particularly useful for searching multiple patterns within a text.

Java Implementation (Illustrative example):

 import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    TrieNode root;

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

    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current.children.putIfAbsent(ch, new TrieNode());
            current = current.children.get(ch);
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return current.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return false;
            }
            current = current.children.get(ch);
        }
        return true;
    }
}

public class TrieExample {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // returns true
        System.out.println(trie.search("app"));     // returns false
        System.out.println(trie.startsWith("app")); // returns true
        trie.insert("app");
        System.out.println(trie.search("app"));     // returns true
    }
} 

Time Complexity: Insertion and search operations take O(m) time, where m is the length of the key. Very efficient for prefix-based searches and searching multiple patterns.

3. String Manipulation

String manipulation involves various operations such as reversing strings, finding substrings, checking for palindromes, and more. These are essential building blocks for many string-related problems.

a. Reversing a String

Java Implementation:

 public class StringReversal {

    public static String reverseString(String str) {
        StringBuilder reversed = new StringBuilder();
        for (int i = str.length() - 1; i >= 0; i--) {
            reversed.append(str.charAt(i));
        }
        return reversed.toString();
    }

    public static void main(String[] args) {
        String original = "Hello";
        String reversed = reverseString(original);
        System.out.println("Original: " + original);
        System.out.println("Reversed: " + reversed);
    }
} 

Time Complexity: O(n), where n is the length of the string.

b. Checking for Palindromes

A palindrome is a string that reads the same forwards and backward.

Java Implementation:

 public class PalindromeCheck {

    public static boolean isPalindrome(String str) {
        str = str.toLowerCase(); // Ignore case
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String palindrome = "Racecar";
        String notPalindrome = "Hello";

        System.out.println(palindrome + " is palindrome: " + isPalindrome(palindrome));
        System.out.println(notPalindrome + " is palindrome: " + isPalindrome(notPalindrome));
    }
} 

Time Complexity: O(n), where n is the length of the string.

c. String Tokenization

String tokenization (splitting a string into words or smaller units) is often necessary for parsing and analyzing text.

Java Implementation (using `String.split()`):

 public class StringTokenization {

    public static void main(String[] args) {
        String text = "This is a sample sentence.";
        String[] tokens = text.split("\\s+"); // Split by whitespace

        for (String token : tokens) {
            System.out.println(token);
        }
    }
} 

Time Complexity: Depends on the implementation and the complexity of the delimiter/regular expression. Generally, the time is linear with the length of the input string in simpler cases, but can become more complex with regular expressions. In simple cases, it will be O(n), where n is the length of string. In more complex use cases with regular expressions it can be much higher.

Conclusion

These are just a few of the fundamental string algorithms and techniques used in competitive programming. Understanding these concepts and their implementations in Java is crucial for tackling string-related problems efficiently. Practice implementing these algorithms and exploring more advanced techniques to enhance your problem-solving skills.