String Hashing

String hashing converts strings to integers for fast comparison and substring operations:

#include <vector>
#include <string>

class StringHash {
private:
    static const int MOD = 1e9 + 7;
    static const int BASE = 31;
    vector<long long> hash_values;
    vector<long long> base_powers;
    
public:
    StringHash(const string& s) {
        int n = s.length();
        hash_values.resize(n + 1, 0);
        base_powers.resize(n + 1, 1);
        
        // Precompute hash values and base powers
        for (int i = 0; i < n; i++) {
            hash_values[i + 1] = (hash_values[i] * BASE + (s[i] - 'a' + 1)) % MOD;
            base_powers[i + 1] = (base_powers[i] * BASE) % MOD;
        }
    }
    
    // Get hash of substring from l to r (inclusive)
    long long getHash(int l, int r) {
        long long result = hash_values[r + 1] - (hash_values[l] * base_powers[r - l + 1]) % MOD;
        return (result % MOD + MOD) % MOD;
    }
    
    // Check if two substrings are equal
    bool areEqual(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

// Find all occurrences of pattern in text using rolling hash
vector<int> rabinKarp(const string& text, const string& pattern) {
    vector<int> occurrences;
    int n = text.length(), m = pattern.length();
    
    if (m > n) return occurrences;
    
    StringHash textHash(text);
    StringHash patternHash(pattern);
    
    long long patternHashValue = patternHash.getHash(0, m - 1);
    
    for (int i = 0; i <= n - m; i++) {
        if (textHash.getHash(i, i + m - 1) == patternHashValue) {
            occurrences.push_back(i);
        }
    }
    
    return occurrences;
}

int main() {
    string text = "ababcababa";
    string pattern = "aba";
    
    vector<int> positions = rabinKarp(text, pattern);
    
    cout << "Pattern found at positions: ";
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;
    
    return 0;
}
                    

Trie Data Structure

Trie (Prefix Tree) efficiently stores and searches strings with common prefixes:

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;
    int wordCount;
    
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
        isEndOfWord = false;
        wordCount = 0;
    }
};

class Trie {
private:
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEndOfWord = true;
        node->wordCount++;
    }
    
    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return node->isEndOfWord;
    }
    
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            node = node->children[index];
        }
        return true;
    }
    
    // Count words with given prefix
    int countWordsWithPrefix(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return 0;
            }
            node = node->children[index];
        }
        
        return countWords(node);
    }
    
private:
    int countWords(TrieNode* node) {
        if (!node) return 0;
        
        int count = node->isEndOfWord ? node->wordCount : 0;
        for (int i = 0; i < 26; i++) {
            count += countWords(node->children[i]);
        }
        return count;
    }
};

int main() {
    Trie trie;
    
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("apply");
    
    cout << "Search 'app': " << trie.search("app") << endl; // true
    cout << "Search 'appl': " << trie.search("appl") << endl; // false
    cout << "Starts with 'app': " << trie.startsWith("app") << endl; // true
    cout << "Words with prefix 'app': " << trie.countWordsWithPrefix("app") << endl; // 4
    
    return 0;
}
                    

KMP Algorithm

Knuth-Morris-Pratt algorithm for efficient pattern matching:

// Compute LPS (Longest Proper Prefix which is also Suffix) array
vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0; // Length of previous longest prefix suffix
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

// KMP pattern searching
vector<int> KMPSearch(const string& text, const string& pattern) {
    vector<int> occurrences;
    int n = text.length();
    int m = pattern.length();
    
    vector<int> lps = computeLPS(pattern);
    
    int i = 0; // Index for text
    int j = 0; // Index for pattern
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            occurrences.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return occurrences;
}

int main() {
    string text = "ABABDABACDABABCABCABCABCABC";
    string pattern = "ABABCABCABCABC";
    
    vector<int> positions = KMPSearch(text, pattern);
    
    cout << "Pattern found at positions: ";
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;
    
    return 0;
}
                    

Z Algorithm

Z algorithm for finding all occurrences of pattern in linear time:

// Compute Z array
vector<int> computeZ(const string& s) {
    int n = s.length();
    vector<int> z(n);
    z[0] = n;
    
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    
    return z;
}

// Find pattern using Z algorithm
vector<int> zSearch(const string& text, const string& pattern) {
    string combined = pattern + "$" + text;
    vector<int> z = computeZ(combined);
    
    vector<int> occurrences;
    int patternLen = pattern.length();
    
    for (int i = patternLen + 1; i < combined.length(); i++) {
        if (z[i] == patternLen) {
            occurrences.push_back(i - patternLen - 1);
        }
    }
    
    return occurrences;
}

// Longest Common Prefix using Z algorithm
int longestCommonPrefix(const string& s1, const string& s2) {
    string combined = s1 + "$" + s2;
    vector<int> z = computeZ(combined);
    
    int maxLCP = 0;
    for (int i = s1.length() + 1; i < combined.length(); i++) {
        maxLCP = max(maxLCP, z[i]);
    }
    
    return maxLCP;
}

int main() {
    string text = "abaaabaaaba";
    string pattern = "aaba";
    
    vector<int> positions = zSearch(text, pattern);
    
    cout << "Pattern found at positions: ";
    for (int pos : positions) {
        cout << pos << " ";
    }
    cout << endl;
    
    cout << "LCP of 'abcdef' and 'abcxyz': " 
         << longestCommonPrefix("abcdef", "abcxyz") << endl; // 3
    
    return 0;
}
                    

Palindrome Algorithms

Efficient algorithms for palindrome detection and counting:

// Manacher's algorithm for finding all palindromes
vector<int> manacher(string s) {
    // Transform string: "abc" -> "^#a#b#c#$"
    string T = "^#";
    for (char c : s) {
        T += c;
        T += '#';
    }
    T += '$';
    
    int n = T.length();
    vector<int> P(n, 0);
    int center = 0, right = 0;
    
    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;
        
        if (i < right) {
            P[i] = min(right - i, P[mirror]);
        }
        
        // Try to expand palindrome centered at i
        while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
            P[i]++;
        }
        
        // If palindrome centered at i extends past right, adjust center and right
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }
    
    return P;
}

// Find longest palindromic substring
string longestPalindrome(string s) {
    vector<int> P = manacher(s);
    
    int maxLen = 0, centerIndex = 0;
    for (int i = 1; i < P.size() - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    
    int start = (centerIndex - maxLen) / 2;
    return s.substr(start, maxLen);
}

// Count palindromic substrings
int countPalindromes(string s) {
    vector<int> P = manacher(s);
    
    int count = 0;
    for (int i = 1; i < P.size() - 1; i++) {
        count += (P[i] + 1) / 2;
    }
    
    return count;
}

// Simple palindrome check for substring
bool isPalindrome(const string& s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++;
        r--;
    }
    return true;
}

// Expand around centers approach
int expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

string longestPalindromeSimple(string s) {
    if (s.empty()) return "";
    
    int start = 0, maxLen = 1;
    
    for (int i = 0; i < s.length(); i++) {
        // Odd length palindromes
        int len1 = expandAroundCenter(s, i, i);
        // Even length palindromes
        int len2 = expandAroundCenter(s, i, i + 1);
        
        int len = max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    
    return s.substr(start, maxLen);
}

int main() {
    string s = "babad";
    
    cout << "Longest palindrome in '" << s << "': " 
         << longestPalindrome(s) << endl;
    
    cout << "Number of palindromic substrings: " 
         << countPalindromes(s) << endl;
    
    return 0;
}
                    

Suffix Array

Suffix arrays provide efficient solutions for many string problems:

// Build suffix array using counting sort
vector<int> buildSuffixArray(string s) {
    s += "$"; // Add sentinel
    int n = s.length();
    
    vector<int> sa(n), rank(n), tmp(n);
    
    // Initial ranking based on characters
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k <<= 1) {
        // Sort by (rank[i], rank[i+k])
        sort(sa.begin(), sa.end(), [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            int ri = (i + k < n) ? rank[i + k] : -1;
            int rj = (j + k < n) ? rank[j + k] : -1;
            return ri < rj;
        });
        
        // Update ranks
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]];
            int pi = sa[i-1], ci = sa[i];
            if (rank[pi] < rank[ci] || 
                (rank[pi] == rank[ci] && 
                 ((pi + k < n ? rank[pi + k] : -1) < 
                  (ci + k < n ? rank[ci + k] : -1)))) {
                tmp[sa[i]]++;
            }
        }
        
        rank = tmp;
    }
    
    return sa;
}

// Build LCP (Longest Common Prefix) array
vector<int> buildLCPArray(const string& s, const vector<int>& sa) {
    int n = s.length();
    vector<int> rank(n), lcp(n - 1);
    
    for (int i = 0; i < n; i++) {
        rank[sa[i]] = i;
    }
    
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
            k++;
        }
        
        lcp[rank[i]] = k;
        if (k > 0) k--;
    }
    
    return lcp;
}

// Count distinct substrings using suffix array
long long countDistinctSubstrings(const string& s) {
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCPArray(s + "$", sa);
    
    int n = s.length();
    long long total = (long long)n * (n + 1) / 2;
    
    for (int x : lcp) {
        total -= x;
    }
    
    return total;
}

int main() {
    string s = "banana";
    
    vector<int> sa = buildSuffixArray(s);
    vector<int> lcp = buildLCPArray(s + "$", sa);
    
    cout << "Suffix Array: ";
    for (int i : sa) {
        cout << i << " ";
    }
    cout << endl;
    
    cout << "Distinct substrings: " << countDistinctSubstrings(s) << endl;
    
    return 0;
}
                    

String Algorithm Applications