Knuth–Morris–Pratt algorithm

Code

Algorithm::prefix_function | String::prefix_function

namespace Algorithm {
    template<typename T>
    std::vector<int32_t> prefix_function(std::span<T> const& s) {
        int32_t n = static_cast<int32_t>(s.size());
        std::vector<int32_t> p(n); p[0] = 0;
        for (int i = 1; i < n; ++i) {
            int32_t j = p[i - 1];
            while (j > 0 && s[j] != s[i]) j = p[j - 1];
            p[i] = (s[i] == s[j]) ? j + 1 : j;
        }
        return p;
    }
}

namespace String {
    std::vector<int> prefix_function(std::string const& s) {
        return Algorithm::prefix_function<char const>({s.begin(), s.length()});
    }
}

Verify

Verification

int main() {
    std::string s; std::cin >> s;
    auto pi = String::prefix_function(s);
    for (auto const& x : pi) std::cout << x << ' ';
}

Input

aabaaab

Output

0 1 0 1 2 2 3

Theory

• In the context of KMP algorithm, the function String::prefix_function is also called failure function.