Prefix Function and KMP

KMP in one sentence

Find every occurrence of a pattern in a text in O(n + m), using one precomputed array — the prefix function.

Definition

Proper prefix — a prefix that is not equal to the entire substring.

Example 1 · s = "abcabcd"

i = 0: s[0...0] = "a"
       Proper prefixes: (none)
       Suffixes: (none)
       π[0] = 0

i = 1: s[0...1] = "ab"
       Proper prefixes: "a"
       Suffixes: "b"
       No match → π[1] = 0

i = 2: s[0...2] = "abc"
       Proper prefixes: "a", "ab"
       Suffixes: "c", "bc"
       No match → π[2] = 0

i = 3: s[0...3] = "abca"
       Proper prefixes: "a", "ab", "abc"
       Suffixes: "a", "ca", "bca"
       Match: "a" → π[3] = 1

i = 4: s[0...4] = "abcab"
       Proper prefixes: "a", "ab", "abc", "abca"
       Suffixes: "b", "ab", "cab", "bcab"
       Match: "ab" → π[4] = 2

i = 5: s[0...5] = "abcabc"
       Proper prefixes: "a", "ab", "abc", "abca", "abcab"
       Suffixes: "c", "bc", "abc", "cabc", "bcabc"
       Match: "abc" → π[5] = 3

i = 6: s[0...6] = "abcabcd"
       Proper prefixes: "a", "ab", "abc", "abca", "abcab", "abcabc"
       Suffixes: "d", "cd", "bcd", "abcd", "cabcd", "bcabcd"
       No match → π[6] = 0

Result: π = [0, 0, 0, 1, 2, 3, 0]

Example 2 · s = "aabaaab"

i = 0: π[0] = 0
i = 1: "aa" → prefix "a" = suffix "a" → π[1] = 1
i = 2: "aab" → no match → π[2] = 0
i = 3: "aaba" → prefix "a" = suffix "a" → π[3] = 1
i = 4: "aabaa" → prefix "aa" = suffix "aa" → π[4] = 2
i = 5: "aabaaa" → prefix "aa" = suffix "aa" → π[5] = 2
i = 6: "aabaaab" → prefix "aab" = suffix "aab" → π[6] = 3

Result: π = [0, 1, 0, 1, 2, 2, 3]

Example 3 · s = "aaaa"

i = 0: π[0] = 0
i = 1: "aa" → prefix "a" = suffix "a" → π[1] = 1
i = 2: "aaa" → prefix "aa" = suffix "aa" → π[2] = 2
i = 3: "aaaa" → prefix "aaa" = suffix "aaa" → π[3] = 3

Result: π = [0, 1, 2, 3]

Naive approach — O(n³)

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

vector<int> prefix_function_naive(string s) {
    int n = s.size();
    vector<int> pi(n);

    pi[0] = 0;  // By definition

    for (int i = 1; i < n; i++) {
        // Try all possible lengths from longest to shortest
        for (int len = i; len > 0; len--) {
            // Check if prefix of length len equals suffix of length len
            bool match = true;
            for (int j = 0; j < len; j++) {
                if (s[j] != s[i - len + 1 + j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                pi[i] = len;
                break;
            }
        }
    }

    return pi;
}

int main() {
    string s = "abcabcd";
    vector<int> pi = prefix_function_naive(s);

    cout << "String: " << s << endl;
    cout << "Prefix function: ";
    for (int i = 0; i < pi.size(); i++)
        cout << pi[i] << " ";
    cout << endl;

    return 0;
}

String: abcabcd
Prefix function: 0 0 0 1 2 3 0

Another version · naive with substr

The same brute force, written with substr: every length from 1 to i, and the last match wins.

#include <iostream>
#include <vector>

using namespace std;

vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> p(n);
    p[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int len = 1; len <= i; len++)
            if (s.substr(0, len) == s.substr(i - len + 1, len))
                p[i] = len;
    }
    return p;
}

int main() {
    string s;
    cin >> s;
    vector<int> p = prefix_function(s);
    for (int i = 0; i < s.size(); i++)
        cout << p[i] << " ";
    return 0;
}

abcabcd

0 0 0 1 2 3 0

Efficient approach — O(n)

1. Start with π[0] = 0
2. For each position i, look at the previous match length j = π[i−1]
3. If s[i] == s[j], then π[i] = j + 1
4. If s[i] != s[j], fall back to j = π[j−1] and try again
5. Continue falling back until a match is found or j reaches 0

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

vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> pi(n);

    pi[0] = 0;  // First element is always 0

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];  // Previous prefix length

        // Fall back until we find a match or reach 0
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        // If characters match, increment the length
        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

int main() {
    string s;
    cout << "Enter string: ";
    cin >> s;

    vector<int> pi = prefix_function(s);

    cout << "\nString:          ";
    for (int i = 0; i < s.size(); i++)
        cout << s[i] << " ";
    cout << endl;

    cout << "Index:           ";
    for (int i = 0; i < s.size(); i++)
        cout << i << " ";
    cout << endl;

    cout << "Prefix function: ";
    for (int i = 0; i < pi.size(); i++)
        cout << pi[i] << " ";
    cout << endl;

    return 0;
}

abcabcd

Enter string: 
String:          a b c a b c d 
Index:           0 1 2 3 4 5 6 
Prefix function: 0 0 0 1 2 3 0

Time: O(n) · Space: O(n)

Step-by-step trace · s = "abcabcd"

i = 0: pi[0] = 0 (by definition)

i = 1:
  j = pi[0] = 0
  s[1] = 'b', s[0] = 'a' → no match
  pi[1] = 0

i = 2:
  j = pi[1] = 0
  s[2] = 'c', s[0] = 'a' → no match
  pi[2] = 0

i = 3:
  j = pi[2] = 0
  s[3] = 'a', s[0] = 'a' → match!
  pi[3] = 1

i = 4:
  j = pi[3] = 1
  s[4] = 'b', s[1] = 'b' → match!
  pi[4] = 2

i = 5:
  j = pi[4] = 2
  s[5] = 'c', s[2] = 'c' → match!
  pi[5] = 3

i = 6:
  j = pi[5] = 3
  s[6] = 'd', s[3] = 'a' → no match
  Fall back: j = pi[2] = 0
  s[6] = 'd', s[0] = 'a' → no match
  pi[6] = 0

Result: π = [0, 0, 0, 1, 2, 3, 0]

Another version · both versions in one file

The brute force and the fast version side by side; main uses the fast one.

// abababaa
#include <iostream>
#include <vector>

using namespace std;

vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> pi(n);
    pi[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int l = 1; l <= i; l++) {
            if (s.substr(0, l) == s.substr(i - l + 1, l))
                pi[i] = l;
        }
    }
    return pi;
}

vector<int> prefix_functionv2(string s) {
    int n = s.size();
    vector<int> pi(n);
    pi[0] = 0;
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main() {
    string s;
    cin >> s;
    vector<int> pi = prefix_functionv2(s);
    for (int i = 0; i < s.size(); i++)
        cout << pi[i] << " ";
    return 0;
}

abababaa

0 0 1 2 3 4 5 1

Problem and idea

Given a text (length n) and a pattern (length m), find all occurrences of the pattern in the text.

• Compute the prefix function of the combined string
• When π[i] equals the pattern length, a match is found
• The separator keeps the pattern from matching across the boundary

KMP implementation

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

vector<int> prefix_function(string s) {
    int n = s.size();
    vector<int> pi(n);
    pi[0] = 0;

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

void KMP(string text, string pattern) {
    // Create combined string: pattern + '#' + text
    string s = pattern + "#" + text;

    int n = s.size();
    int m = pattern.size();

    // Compute prefix function
    vector<int> pi = prefix_function(s);

    // Find all occurrences
    for (int i = m + 1; i < n; i++) {
        // If prefix length equals pattern length, we found a match
        if (pi[i] == m) {
            // Position in text = i - m - m
            int pos = i - 2 * m;
            cout << "Pattern found at index " << pos << endl;
        }
    }
}

int main() {
    string text, pattern;

    cout << "Enter text: ";
    cin >> text;

    cout << "Enter pattern: ";
    cin >> pattern;

    cout << "\nSearching for pattern in text...\n" << endl;
    KMP(text, pattern);

    return 0;
}

ababcabcabababd
ababd

Enter text: Enter pattern: 
Searching for pattern in text...

Pattern found at index 10

Example · text = "ababcabcabababd", pattern = "ababd"

s = "ababd#ababcabcabababd"

Index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
String: a b a b d # a b a b c  a  b  c  a  b  a  b  a  b  d 
π:      0 0 1 2 0 0 1 2 3 4 0  1  2  0  1  2  3  4  3  4  5 

π[20] = 5: position in text = 20 - 2×5 = 10

text  = "ababcabcabababd"
index    012345678901234
                   ^^^^^   (index 10–14: "ababd")

Another example · text = "aabaacaabaa", pattern = "aaba"

s = "aaba#aabaacaabaa"

Index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
String: a a b a # a a b a a c  a  a  b  a  a 
π:      0 1 0 1 0 1 2 3 4 2 0  1  2  3  4  2 

π[8] = 4 → position = 8 - 2×4 = 0
π[14] = 4 → position = 14 - 2×4 = 6

text  = "aabaacaabaa"
index    01234567890
         ^^^^   (index 0–3: "aaba")
               ^^^^   (index 6–9: "aaba")

Time complexity

1 · Pattern matching

Find all occurrences of a pattern: create pattern + '#' + text and compute the prefix function.

void find_all_occurrences(string text, string pattern) {
    string s = pattern + "#" + text;
    vector<int> pi = prefix_function(s);
    int m = pattern.size();

    cout << "Pattern found at positions: ";
    for (int i = m + 1; i < s.size(); i++) {
        if (pi[i] == m) {
            cout << (i - 2 * m) << " ";
        }
    }
    cout << endl;
}

2 · Counting occurrences, overlapping included

Count how many times π[i] equals the pattern length.

int count_occurrences(string text, string pattern) {
    string s = pattern + "#" + text;
    vector<int> pi = prefix_function(s);
    int m = pattern.size();
    int count = 0;

    for (int i = m + 1; i < s.size(); i++) {
        if (pi[i] == m) {
            count++;
        }
    }

    return count;
}

// Example: text = "aaaa", pattern = "aa"
// s = "aa#aaaa"
// Occurrences at: 0, 1, 2 → count = 3

text = "aaaa", pattern = "aa"
s = "aa#aaaa"
Occurrences at: 0, 1, 2 → count = 3

3 · Shortest period of a string

"abcabcabc" has period "abc" — length 3.

int shortest_period(string s) {
    int n = s.size();
    vector<int> pi = prefix_function(s);

    int len = n - pi[n - 1];  // Length of shortest period

    // Check if string is actually periodic
    if (n % len == 0) {
        return len;
    } else {
        return n;  // No period (entire string)
    }
}

// Example: s = "abcabcabc"
// pi[8] = 6 (prefix "abcabc" = suffix "abcabc")
// len = 9 - 6 = 3
// 9 % 3 == 0 → period length is 3

s = "abcabcabc"
pi[8] = 6 (prefix "abcabc" = suffix "abcabc")
len = 9 - 6 = 3
9 % 3 == 0 → period length is 3

• If π[n−1] = k, the first k characters match the last k
• The shortest period has length n − k
• If n is divisible by n − k, the string is periodic

4 · String compression

Can the string be written as a repeated pattern? Check whether the shortest period divides its length.

string compress(string s) {
    int n = s.size();
    int period_len = shortest_period(s);

    if (period_len < n) {
        int count = n / period_len;
        string pattern = s.substr(0, period_len);
        return pattern + " × " + to_string(count);
    }

    return s;  // Cannot compress
}

// Example: "abcabcabc" → "abc × 3"
// Example: "abcdef" → "abcdef" (no compression)

"abcabcabc" → "abc × 3"
"abcdef"    → "abcdef" (period 6 = whole string, no compression)

5 · Pattern in a cyclic string

Does the pattern occur in some rotation of the text? Search in text + text.

bool pattern_in_rotation(string text, string pattern) {
    string doubled = text + text;
    string s = pattern + "#" + doubled;
    vector<int> pi = prefix_function(s);
    int m = pattern.size();

    for (int i = m + 1; i < s.size(); i++) {
        if (pi[i] == m) {
            return true;
        }
    }

    return false;
}

// Example: text = "abcde", pattern = "dea"
// s = "dea#abcdeabcde"
// Pattern "dea" found → true

text = "abcde", pattern = "dea"
s = "dea#abcdeabcde"
"dea" found at index 3 of the doubled text → true

6 · Longest palindromic prefix

Compute the prefix function of s + '#' + reverse(s); the last value is the answer.

int longest_palindrome_prefix(string s) {
    string rev = s;
    reverse(rev.begin(), rev.end());

    string combined = s + "#" + rev;
    vector<int> pi = prefix_function(combined);

    return pi[combined.size() - 1];
}

// Example: s = "abacaba"
// rev = "abacaba"
// combined = "abacaba#abacaba"
// π[14] = 7 → entire string is palindrome

s = "abacaba", rev = "abacaba"
combined = "abacaba#abacaba"
π[14] = 7 → the entire string is a palindrome

7 · All borders

All lengths k for which the prefix of length k equals the suffix of length k: start from π[n−1] and keep jumping back.

vector<int> find_all_borders(string s) {
    int n = s.size();
    vector<int> pi = prefix_function(s);
    vector<int> borders;

    int k = pi[n - 1];
    while (k > 0) {
        borders.push_back(k);
        k = pi[k - 1];
    }

    reverse(borders.begin(), borders.end());
    return borders;
}

// Example: s = "abcabcab"
// Borders: lengths 2, 5 ("ab", "abcab")

s = "abcabcab"
Borders: lengths 2, 5 ("ab", "abcab")

8 · Several patterns

For each pattern, build its own pattern + '#' + text.

void find_multiple_patterns(string text, vector<string> patterns) {
    for (int k = 0; k < patterns.size(); k++) {
        string s = patterns[k] + "#" + text;
        vector<int> pi = prefix_function(s);
        int m = patterns[k].size();

        for (int i = m + 1; i < s.size(); i++) {
            if (pi[i] == m) {
                cout << "Pattern " << k << " (\"" << patterns[k];
                cout << "\") found at index " << (i - 2 * m) << endl;
                break;  // Found first occurrence
            }
        }
    }
}

Q1 · Why do we need the separator '#'?

Without it the pattern could match across the boundary between the pattern and the text, giving wrong results.

pattern = "ab", text = "cab"
Without #: "abcab" → would match at position 0 (wrong!)
With #:    "ab#cab" → no match (correct!)

In "abcab", π[4] = 2 = m, so the formula reports position 4 − 2×2 = 0 — but in "cab" the pattern starts at index 1.

Q2 · What if '#' appears in the text or the pattern?

Choose a separator that appears in neither:

• '#' if only letters are used
• '$' for printable ASCII
• any character with a code larger than every character of the alphabet

Q3 · Why is this simpler than traditional KMP?

Traditional KMP moves a pointer in the pattern and a pointer in the text and has to handle both carefully. The combined string reduces it to one loop that checks π[i] == m.

Q4 · Can we save space?

Yes — the prefix function can be computed on the fly without storing the whole combined string, but the code becomes more complex.

Q5 · Why is the prefix function O(n)?

There is a while loop inside the for loop, but j grows by at most 1 per iteration — at most n times in total — so it can also decrease at most n times in total. Overall: O(n).

Eight things to remember

1. The prefix function is the key — the longest proper prefix that is also a suffix
2. Pattern matching with pattern + '#' + text — elegant and simple
3. O(n + m) guaranteed — no worst-case degradation
4. When π[i] = m, the pattern is found — at position i − 2m
5. The separator '#' is essential — it prevents false matches
6. The prefix function is O(n)
7. Many applications — periods, compression, palindromes
8. No false positives — unlike hashing

Try these

1. Implement KMP to find all occurrences of a pattern in a text
2. Find the shortest period of a string
3. Count overlapping pattern occurrences
4. Check if a string is a concatenation of a repeated substring
5. Find the longest palindromic prefix using the prefix function
6. Find if a pattern exists in any rotation of a string
7. Compress a string using a repeating pattern
8. Find all borders of a string
9. Count how many times each pattern appears in a text
10. Find the lexicographically smallest rotation of a string

Problem to topic