Knuth-Morris-Pratt Algorithm
(content/string/kmp.h)

• View this file on GitHub
• Last update: 2024-02-01 17:09:56-05:00

pi[i] = the length of the longest proper prefix of s (i.e. s[0, i-1]) that is also a suffix of s[0, i-1].

To check if t contains s, do kmp on s+'#'+t and check whether any pi[i] = len(s).

Depends on

• My starter code (content/utils/template.h)

Code

#pragma once
#include "../utils/template.h"

/**
 * @brief Knuth-Morris-Pratt Algorithm
 * @docs docs/kmp.md
 */

vector<int> kmp(string s){
	vector<int> pi(size(s));
	pi[0] = 0;
	for(int i = 1, j = 0; i < size(s); i++){
		while(j and s[i] != s[j])
			j = pi[j-1];
		if(s[i] == s[j])
			j++;
		pi[i] = j;
	}
	return pi;
}

#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/string/kmp.h"

/**
 * @brief Knuth-Morris-Pratt Algorithm
 * @docs docs/kmp.md
 */

vector<int> kmp(string s){
	vector<int> pi(size(s));
	pi[0] = 0;
	for(int i = 1, j = 0; i < size(s); i++){
		while(j and s[i] != s[j])
			j = pi[j-1];
		if(s[i] == s[j])
			j++;
		pi[i] = j;
	}
	return pi;
}

Back to top page