Manacher's Algorithm

Purpose

Manacher's algorithm computes the longest palindromic substring centered at each position (including positions between characters for even-length palindromes) in O(n) time complexity.

Naive Approach

The naive method examines each center position and attempts to expand outward character by character until the characters no longer match. The expansion loop appears as follows, where s is the character array, center is the current center position, and radius stores the palindrome radius:

while (s[center - radius - 1] == s[center + radius + 1]) ++radius;

Preprocessing Step

Insert distinct sentinel characters at the boundaries and betwean every pair of original characters. For the string abcdefg, a valid preprocessed form is:

@#a#b#c#d#e#f#g#$

Three distinct sentinel characters are used:

• The # characters allow detection of even-length palindromes in the original string (e.g., a#a represents palindrome aa)
• The @ and $ sentinels at boundaries ensure the algorithm terminates without special case handling, as they can never be part of a valid palindrome

Algorithm Execution

Maintain variable right representing the rightmost position covered by previously computed palindromes, and center representing the palindrome that achieved this rightmost position.

When processing position i:

• If i >= right, apply the naive expansion directly
• Otherwise, initialize radius[i] using the mirrored position's value: radius[i] = min(radius[2 * center - i], right - i)

This initialization works because the palindrome centered at the mirrored position is fully contained within the current rightmost palindrome. However, when the mirrored position's palindrome extends beyond right, the initial value must be clamped to right - i to ensure validity.

Complexity Analysis

Three cases determine overall complexity:

• Case 1: i >= right — naive expansion performed, contributing to right advancement
• Case 2: i < right and palindrome fully contained — initial value equals final value, single expansion check
• Case 3: i < right but palindrome extends beyond right — expansion proceeds from right

Since right advances at most n positions total, the algorithm runs in O(n) time.

Implementation

int right = 0, center = 0;

void expand(int pos) {
    while (s[pos - radius[pos] - 1] == s[pos + radius[pos] + 1]) {
        ++radius[pos];
    }
    if (right < pos + radius[pos]) {
        right = pos + radius[pos];
        center = pos;
    }
}

for (int i = 1; i <= total; ++i) {
    if (i <= right) {
        int mirrored = 2 * center - i;
        radius[i] = min(radius[mirrored], right - i);
    }
    expand(i);
}

AC Automaton

Overview

The Aho-Corasick automaton combines a trie structure with failure links (derived from KMP) to enable efficient multi-pattern matching in linear time. This implementation uses difference arrays on the failure tree to count pattern occurrences.

Failure Tree Difference Array

The failuree tree approach counts how many patterns terminate at each node in the text. During text traversal, increment the counter at each visited node. Then perform a subtree sum from children to parent to aggregate counts.

Consider matching pattern abba against text containing abba and bb. After traversing from position 1 to position 5, the failure link at node 5 points back to node 2, preventing the bb pattern from matching incorrectly.

Critical Implementation Note: Failure links must be built using BFS, not DFS, to ensure corrrect parent-child relationships in the failure tree.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 200000;
const int MAX_CHARS = 2000000;

struct AhoCorasick {
    struct Node {
        int next[26];
        int fail;
        
        void initialize() {
            fail = 1;
            memset(next, 0, sizeof(next));
        }
    };
    
    vector<Node> nodes;
    int nodeCount = 1;
    vector<int> head, to, nxt;
    vector<int> diffArray;
    queue<int> bfsQueue;
    
    AhoCorasick(int size = MAX_NODES) {
        nodes.resize(size + 5);
        nodes[1].initialize();
        head.assign(MAX_CHARS + 5, 0);
        to.assign(MAX_CHARS * 2 + 5, 0);
        nxt.assign(MAX_CHARS * 2 + 5, 0);
        diffArray.assign(MAX_CHARS + 5, 0);
    }
    
    void addEdge(int parent, int child) {
        nxt[++nodeCount] = head[parent];
        to[nodeCount] = child;
        head[parent] = nodeCount;
    }
    
    void insertPattern(const char* pattern, int patternId) {
        int current = 1;
        for (int i = 1; pattern[i]; ++i) {
            int idx = pattern[i] - 'a';
            if (!nodes[current].next[idx]) {
                nodes[current].next[idx] = ++nodeCount;
                nodes[nodeCount].initialize();
            }
            current = nodes[current].next[idx];
        }
        terminal[current] = patternId;
    }
    
    void buildFailureLinks() {
        bfsQueue.push(1);
        
        while (!bfsQueue.empty()) {
            int current = bfsQueue.front();
            bfsQueue.pop();
            
            if (current != 1) {
                addEdge(nodes[current].fail, current);
            }
            
            for (int i = 0; i < 26; ++i) {
                if (nodes[current].next[i]) {
                    int child = nodes[current].next[i];
                    
                    if (current == 1) {
                        nodes[child].fail = 1;
                    } else {
                        int fail = nodes[current].fail;
                        while (fail != 1 && !nodes[fail].next[i]) {
                            fail = nodes[fail].fail;
                        }
                        if (nodes[fail].next[i]) {
                            fail = nodes[fail].next[i];
                        }
                        nodes[child].fail = fail;
                    }
                    bfsQueue.push(child);
                }
            }
        }
    }
    
    void processText(const char* text, int length) {
        int current = 1;
        for (int i = 1; i <= length; ++i) {
            int idx = text[i] - 'a';
            while (current != 1 && !nodes[current].next[idx]) {
                current = nodes[current].fail;
            }
            if (nodes[current].next[idx]) {
                current = nodes[current].next[idx];
            }
            ++diffArray[current];
        }
    }
    
    void aggregateCounts(int node = 1) {
        for (int edge = head[node]; edge; edge = nxt[edge]) {
            int child = to[edge];
            aggregateCounts(child);
            diffArray[node] += diffArray[child];
        }
    }
    
private:
    vector<int> terminal;
};

int main() {
    int n;
    scanf("%d", &n);
    
    AhoCorasick automaton;
    vector<pair<const char*, int>> patterns;
    
    for (int i = 1; i <= n; ++i) {
        char buffer[MAX_CHARS];
        scanf("%s", buffer + 1);
        patterns.emplace_back(buffer, i);
        automaton.insertPattern(buffer, i);
    }
    
    char text[MAX_CHARS];
    scanf("%s", text + 1);
    int textLength = strlen(text + 1);
    
    automaton.buildFailureLinks();
    automaton.processText(text, textLength);
    automaton.aggregateCounts();
    
    for (int i = 1; i <= n; ++i) {
        printf("%d\n", automaton.diffArray[automaton.terminal[i]]);
    }
    
    return 0;
}

The algorithm builds the failure links using BFS, then processes the text in a single pass. The difference array accumulates counts up the failure tree, yielding the number of occurrences for each pattern.