Knuth–Morris–Pratt (KMP) Algorithm

KMP finds every occurrence of a pattern in a text in guaranteed linear time. Its key state is how many initial pattern characters already match the end of the processed text. When the next character disagrees, the pattern’s prefix array tells us which shorter partial match can still survive. The text index never moves backward.

The prefix function is a property of one string; KMP is an application that preprocesses the pattern and then scans another string. This lesson focuses on that scanning invariant, correct overlapping matches, and why a completed match must also use a failure link. The implementation compares bytes exactly, accepts spaces, and gives the empty pattern an explicit meaning.

Prerequisites: Naive String Matching; Prefix Function (π Array), including the border-chain fallback rule.

Build the idea

1. 1. Reuse the pattern’s borders

   Let P=aba. Its prefix array is 0 0 1. If three text characters have matched aba, their final a is already the beginning of a possible next aba. Starting over with no memory would throw away this overlap. More generally, if j pattern characters have just matched, a smaller surviving partial match must be a border of P[0..j), so its next candidate length is π[j−1].

   Build π only for P, not for the text. The same preprocessing can then be reused when searching many texts with that fixed pattern. This implementation does not concatenate strings or choose a separator character, so no ordinary input character can accidentally conflict with a separator.

2. 2. Maintain a matched-prefix state

   Before reading text position i, j is the length of the longest proper pattern prefix equal to a suffix of the already processed text, after any complete match has been reported. If text[i] differs from P[j], follow j=π[j−1] while j>0 and try again. Every fallback preserves a suffix that is already known to match; only the next character needs checking.

   When text[i]=P[j], increment j. If j=0 and the characters differ, keep zero and consume this text character: no nonempty prefix ends here. The same text[i] may be compared against several pattern positions, but it is never skipped during fallback. Moving the text index backward is unnecessary because all shorter candidates are already represented by j.

3. 3. Trace a mismatch without restarting

   For P=ababaca, suppose the processed text ends with ababa, so j=5. The next text character is b, but P[5]=c. Fall back to π[4]=3. Now P[3]=b agrees, so increase j to 4. The new useful suffix is abab; the earlier matched prefix was not wasted.

   The border chain is complete: any candidate that could still match must be a border of the previously matched block. Descending through its prefix-array links tries these candidates from longest to shortest, so the first extension produces the longest possible new state.

4. 4. Report occurrences and preserve overlaps

   When j reaches M, a full match ends at i and begins at i−M+1. Record that starting position, then immediately set j=π[M−1]. This both preserves a useful overlap and prevents the next iteration from reading P[M], which lies beyond the pattern.

   For T=ababa aba and P=aba, states after the first three characters reach 1,2,3 and report start 0. Fallback gives j=1. The next b and a complete a second occurrence at start 2. The space resets any surviving nonempty prefix, and the final aba reports start 6. Output positions are 0,2,6. Matches overlapping one another are counted separately.

5. 5. Justify the linear bound and edge cases

   During the scan, successful extensions increase j by one, at most N times. Every mismatch fallback strictly decreases j; completed-match fallback also decreases it. The total amount of decrease cannot exceed all previous increases. Consequently there are O(N) fallback iterations in total, even though the code contains a loop inside a loop. Prefix preprocessing separately costs O(M), yielding O(N+M) overall search time.

   If P is empty, the normal scan must not access P[0]. Handle it first by returning boundaries 0 through N. Empty T with nonempty P has no matches; a pattern longer than T cannot reach state M. One-character patterns, all-equal strings, and a match ending at the final text character need no special scanning cases. For actual streaming input, keep j between chunks and translate local indices into global positions; the algorithm’s state does not require retaining old text.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int>prefixFunction(const string&pattern){
    int m=static_cast<int>(pattern.size());
    vector<int>pi(m,0);
    for(int i=1;i<m;++i){
        int j=pi[i-1];
        while(j>0&&pattern[i]!=pattern[j]){
            j=pi[j-1];
        }
        if(pattern[i]==pattern[j]){
            ++j;
        }
        pi[i]=j;
    }
    return pi;
}
vector<int>findMatches(const string&text,const string&pattern){
    int n=static_cast<int>(text.size()),m=static_cast<int>(pattern.size());
    vector<int>matches;
    if(m==0){ // The empty pattern matches every text boundary.
        for(int i=0;i<=n;++i){
            matches.push_back(i);
        }
        return matches;
    }
    vector<int>pi=prefixFunction(pattern); // Preprocess only the pattern.
    int j=0; // Pattern-prefix length matching the processed text suffix.
    for(int i=0;i<n;++i){
        while(j>0&&text[i]!=pattern[j]){
            j=pi[j-1]; // Reuse a smaller border without moving i backward.
        }
        if(text[i]==pattern[j]){
            ++j;
        }
        if(j==m){
            matches.push_back(i-m+1); // Convert ending index into starting index.
            j=pi[m-1]; // Retain overlaps and keep the next pattern index valid.
        }
    }
    return matches;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string text,pattern;
    getline(cin,text);
    getline(cin,pattern); // Whitespace remains meaningful.
    vector<int>matches=findMatches(text,pattern);
    cout<<matches.size()<<'\n';
    if(matches.empty()){
        cout<<-1<<'\n';
    }
    else{
        for(int i=0;i<static_cast<int>(matches.size());++i){
            cout<<matches[i]<<(i+1==static_cast<int>(matches.size())?'\n':' ');
        }
    }
}

Complexity analysis

O(M) preprocessing and O(N) scanning, plus O(K) reporting for K matches. Total O(N+M+K), which is O(N+M+1) because K≤N+1. The prefix array uses O(M) auxiliary space; returned positions use O(K); this complete program also stores O(N+M) input. Streaming the text can avoid its O(N) storage.

Example input and output

Line 1: text T. Line 2: pattern P. Each line may be empty or contain spaces and has length at most 1,000,000. Print occurrence count, then all 0-based starting positions, or −1 on the second line if none. Empty P matches all N+1 boundaries.

Input

ababa aba
aba

Output

3
0 2 6

Occurrences at 0 and 2 overlap; the final occurrence starts after the space at position 6. The space is an ordinary mismatching input byte, not ignored.

Practical applications

Guaranteed linear exact matching, searching repeated patterns, scanning data in chunks, and counting overlapping occurrences. Unlike probabilistic hashing, character comparisons produce exact matches without collision concerns. For many distinct patterns simultaneously, study Aho–Corasick rather than independently scanning all patterns blindly.

Check your understanding

After reporting a match of a nonempty pattern of length M, which state should KMP retain?

Put it into practice

Adapt the function to count occurrences without storing their positions, while preserving the empty-pattern convention.