Manacher's Algorithm

Implementation for finding the longest palindromic substring:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> manacher(const string &s) {
    string t = "#";
    for(char c : s) t += c, t += '#';
    
    int n = t.size();
    vector<int> p(n);
    int center = 0, right = 0;
    
    for(int i = 1; i < n; i++) {
        int mirror = 2*center - i;
        if(i < right) p[i] = min(right-i, p[mirror]);
        
        while(i + p[i] + 1 < n && i - p[i] - 1 >= 0 && 
              t[i+p[i]+1] == t[i-p[i]-1]) p[i]++;
        
        if(i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    return p;
}

Example Problems

1. Entisymmetry Check: Modify equality check to opposite characters
2. Longest Double Palindrome: Find two adjacent palindromes with maximum combined length
3. Palindrome Matching: Combine KMP with Manacehr for efficient pattern matching

KMP and Extended KMP

KMP Implementation

vector<int> computeLPS(const string &pattern) {
    vector<int> lps(pattern.size());
    int len = 0;
    
    for(int i = 1; i < pattern.size(); ) {
        if(pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else {
            if(len) len = lps[len-1];
            else lps[i++] = 0;
        }
    }
    return lps;
}

Extended KMP (Z-Algorithm)

vector<int> zAlgorithm(const string &s) {
    int n = s.size();
    vector<int> z(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;
}

Suffix Arrays

Construction with Radix Sort

vector<int> buildSuffixArray(const string &s) {
    int n = s.size();
    vector<int> sa(n), rk(n), tmp(n);
    
    for(int i = 0; i < n; i++) {
        sa[i] = i;
        rk[i] = s[i];
    }
    
    for(int k = 1; k < n; k *= 2) {
        auto cmp = [&](int i, int j) {
            if(rk[i] != rk[j]) return rk[i] < rk[j];
            int ri = i+k < n ? rk[i+k] : -1;
            int rj = j+k < n ? rk[j+k] : -1;
            return ri < rj;
        };
        
        sort(sa.begin(), sa.end(), cmp);
        
        tmp[sa[0]] = 0;
        for(int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        }
        
        rk = tmp;
    }
    
    return sa;
}

Height Array Construtcion

vector<int> buildHeightArray(const string &s, const vector<int> &sa) {
    int n = s.size();
    vector<int> lcp(n), rank(n);
    
    for(int i = 0; i < n; i++) rank[sa[i]] = i;
    
    int h = 0;
    for(int i = 0; i < n; i++) {
        if(rank[i] > 0) {
            int j = sa[rank[i]-1];
            
            while(i+h < n && j+h < n && s[i+h] == s[j+h]) h++;
            
            lcp[rank[i]] = h;
            if(h > 0) h--;
        }
    }
    
    return lcp;
}

Applications

1. Pattern Matching: Use suffix arrays for efficient substring search
2. Longest Common Substring: Find maximum LCP between any two suffixes
3. Distinct Substrings: Calculate unique substrings using suffix array and LCP

Advanced Topics

1. Suffix Automata: Linear-size automaton for all suffixes
2. Palindrome Series: Efficient palindrome counting and analysis
3. Border Theory: Properties and applications of string borders