string/kmp.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>

using namespace std;

//Preprocessing Substring sub for KMP-Search
vector<int> kmp_preprocessing(string& sub) {
	vector<int> b(sub.size() + 1);
	b[0] = -1;
	int i = 0, j = -1;
	while(i < sub.size()) {
		while(j >= 0 && sub[i] != sub[j])
			j = b[j];
		i++; j++;
		b[i] = j;
	}
	return b;
}

//Searching after Substring sub in s
vector<int> kmp_search(string& s, string& sub) {
	vector<int> pre = kmp_preprocessing(sub);
	vector<int> result;
	int i = 0, j = -1;
	while(i < s.size()) {
		while(j >= 0 && s[i] != sub[j])
			j = pre[j];
		i++; j++;
		if(j == sub.size()) {
			result.push_back(i-j);
			j = pre[j];
		}
	}
	return result;
}