1#include <bits/stdc++.h>
2using namespace std;
3
4vector<int> buildLPS(const string& p) {
5 int m = p.size(); vector<int> lps(m, 0);
6 int len = 0;
7 for (int i = 1; i < m; ) {
8 if (p[i] == p[len]) lps[i++] = ++len;
9 else if (len) len = lps[len - 1];
10 else lps[i++] = 0;
11 }
12 return lps;
13}
14
15vector<int> kmpSearch(const string& text, const string& pat) {
16 vector<int> lps = buildLPS(pat), matches;
17 int n = text.size(), m = pat.size(), i = 0, j = 0;
18 while (i < n) {
19 if (text[i] == pat[j]) { ++i; ++j;
20 if (j == m) { matches.push_back(i - j); j = lps[j - 1]; }
21 } else if (j) j = lps[j - 1];
22 else ++i;
23 }
24 return matches;
25}
