Knuth-Morris-Pratt
(string/kmp.hpp)

• View this file on GitHub
• Last update: 2026-07-13 04:27:33+09:00
• Include: #include "string/kmp.hpp"

Overview

The prefix function stores, for every prefix ending at position i, the length of its longest proper prefix that is also a suffix. Knuth-Morris-Pratt uses it to find every occurrence of a pattern without backing up in the text.

Both functions are generic over indexable sequences with comparable elements.

Functions

Function	Description	Complexity
vector<int> prefix_function(const Sequence& sequence)	Returns the prefix-function array.	$O(N)$
vector<int> kmp_search(const Text& text, const Pattern& pattern)	Returns every occurrence’s starting index, including overlapping matches.	$O(N + M)$

An empty pattern occurs at every position from 0 through text.size().

Example

#include "string/kmp.hpp"

#include <iostream>
#include <string>

int main() {
    std::string text = "ababa";
    std::string pattern = "aba";

    for (int position : m1une::string::kmp_search(text, pattern)) {
        std::cout << position << "\n"; // 0, then 2
    }
}

Required by

• String Algorithms Bundle (string/all.hpp)

Verified with

• verify/string/kmp.test.cpp
• verify/string/string_algorithms.test.cpp

Code

#ifndef M1UNE_STRING_KMP_HPP
#define M1UNE_STRING_KMP_HPP 1

#include <vector>

namespace m1une {
namespace string {

// Returns the KMP prefix function.
template <class Sequence>
std::vector<int> prefix_function(const Sequence& sequence) {
    int n = int(sequence.size());
    std::vector<int> prefix(n);
    for (int i = 1; i < n; i++) {
        int j = prefix[i - 1];
        while (j > 0 && sequence[i] != sequence[j]) {
            j = prefix[j - 1];
        }
        if (sequence[i] == sequence[j]) j++;
        prefix[i] = j;
    }
    return prefix;
}

// Returns every starting position where pattern occurs in text.
// An empty pattern occurs at every position from 0 through text.size().
template <class Text, class Pattern>
std::vector<int> kmp_search(const Text& text, const Pattern& pattern) {
    int n = int(text.size());
    int m = int(pattern.size());
    if (m == 0) {
        std::vector<int> occurrences(n + 1);
        for (int i = 0; i <= n; i++) occurrences[i] = i;
        return occurrences;
    }

    std::vector<int> prefix = prefix_function(pattern);
    std::vector<int> occurrences;
    int matched = 0;
    for (int i = 0; i < n; i++) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = prefix[matched - 1];
        }
        if (text[i] == pattern[matched]) matched++;
        if (matched == m) {
            occurrences.push_back(i - m + 1);
            matched = prefix[matched - 1];
        }
    }
    return occurrences;
}

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_KMP_HPP

#line 1 "string/kmp.hpp"



#include <vector>

namespace m1une {
namespace string {

// Returns the KMP prefix function.
template <class Sequence>
std::vector<int> prefix_function(const Sequence& sequence) {
    int n = int(sequence.size());
    std::vector<int> prefix(n);
    for (int i = 1; i < n; i++) {
        int j = prefix[i - 1];
        while (j > 0 && sequence[i] != sequence[j]) {
            j = prefix[j - 1];
        }
        if (sequence[i] == sequence[j]) j++;
        prefix[i] = j;
    }
    return prefix;
}

// Returns every starting position where pattern occurs in text.
// An empty pattern occurs at every position from 0 through text.size().
template <class Text, class Pattern>
std::vector<int> kmp_search(const Text& text, const Pattern& pattern) {
    int n = int(text.size());
    int m = int(pattern.size());
    if (m == 0) {
        std::vector<int> occurrences(n + 1);
        for (int i = 0; i <= n; i++) occurrences[i] = i;
        return occurrences;
    }

    std::vector<int> prefix = prefix_function(pattern);
    std::vector<int> occurrences;
    int matched = 0;
    for (int i = 0; i < n; i++) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = prefix[matched - 1];
        }
        if (text[i] == pattern[matched]) matched++;
        if (matched == m) {
            occurrences.push_back(i - m + 1);
            matched = prefix[matched - 1];
        }
    }
    return occurrences;
}

}  // namespace string
}  // namespace m1une

Back to top page