【模板】kmp

引理：当计算第 \(i\) 位的失配指针时，若 \(j_0\) 是一个候选条件，那么小于 \(j_0\) 的最大候选条件是 \(fail[j_0]\)。

证明：反证法。假设存在 \(j_1\)，使得\(fail[j_0]<j_1<j_0\)，那么\(s[1,j_0]=s[i-j_0+1,i]，s[i,j_1]=s[i-j_1+1,i]，s[j_0-j_1+1,j_0]=s[i-j_1+1,i]\)，可知\(s[1,j_1]=s[j_0-j_1+1]\)，根据\(fail[\ ]\)数组的极大性可知产生了矛盾，证毕。

时间复杂度为\(O(n)\)

代码如下

// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0), cout.tie(0);

	string s, t;

	cin >> s >> t;

	int n = s.size(), m = t.size();

	vector<int> fail(m, -1);

	auto getfail = [&]() {

		for (int i = 1, j = -1; i < m; i++) {

			while (j != -1 && t[j + 1] != t[i]) {

				j = fail[j];

			}

			if (t[j + 1] == t[i]) {

				++j;

			}

			fail[i] = j;

		}

	};

	getfail();

	auto match = [&]() {

		for (int i = 0, j = -1; i < n; i++) {

			while (j != -1 && t[j + 1] != s[i]) {

				j = fail[j];

			}

			if (t[j + 1] == s[i]) {

				++j;

			}

			if (j == m - 1) {

				cout << i - m + 2 << endl;

			}

		}

	};

	match();

	for (auto v : fail) {

		cout << v + 1 << " ";

	}

	cout << endl;

	return 0;

}

巴特西

【模板】kmp

最新文章

热门文章