KMP algorithm (string/kmp.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-05-25 14:58:25+09:00

なにこれ

文字列中にある文字列（パターン）が存在するか判定する．

関数

文字列 S 中に現れる文字列 T の頭文字のインデックスを格納する配列 ans を返す．

計算量

• $P(|S|+|T|)$

Verified with

• test/aoj_ALDS1_14_B.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<int> KMP(const string &S, const string &T) {
	vector<int> ans;
	vector<int> nxt_idx(T.length() + 1, 0);
	nxt_idx[0] = -1;

	for(int i = 1, j = -1; i <= T.length(); i++) {
		while(j >= 0 && T[i - 1] != T[j]) j = nxt_idx[j];
		j++;
		if(i < T.length() && T[i] == T[j]) nxt_idx[i] = nxt_idx[j];
		else
			nxt_idx[i] = j;
	}

	for(int i = 0, j = 0; i < S.length(); i++) {
		while(j >= 0 && S[i] != T[j]) j = nxt_idx[j];
		j++;
		if(j == T.length()) {
			ans.emplace_back(i - j + 1);
			j = nxt_idx[j];
		}
	}

	return ans;
}

#line 2 "string/kmp.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

vector<int> KMP(const string &S, const string &T) {
	vector<int> ans;
	vector<int> nxt_idx(T.length() + 1, 0);
	nxt_idx[0] = -1;

	for(int i = 1, j = -1; i <= T.length(); i++) {
		while(j >= 0 && T[i - 1] != T[j]) j = nxt_idx[j];
		j++;
		if(i < T.length() && T[i] == T[j]) nxt_idx[i] = nxt_idx[j];
		else
			nxt_idx[i] = j;
	}

	for(int i = 0, j = 0; i < S.length(); i++) {
		while(j >= 0 && S[i] != T[j]) j = nxt_idx[j];
		j++;
		if(j == T.length()) {
			ans.emplace_back(i - j + 1);
			j = nxt_idx[j];
		}
	}

	return ans;
}

Back to top page