前缀表 + kmp

1. 求前缀表的核心就是 知道在 字符串‘’A B …. C D‘’中

   求 最长公共前后缀长度

   已知 A B互相相同,C D 互相相同, (A + B)和(C+D)互相相同

   得到A和D互相相同

2. prefix_table右移一下,

3. 扫描文本串时,pattern串,根据prefix_table的下标位置来改变指向pattern串的指针

#include <bits/stdc++.h>
using namespace std;

// 求前缀表
vector<int> prefix_table(string s) {
	int n = s.length();
	vector<int> prefix(n);
	for (int i=1; i<n; ++i) {
		int len = prefix[i - 1];
		while(len > 0 && s[i] != s[len])
			len = prefix[len - 1];
		if (s[i] == s[len])
			len++;
		prefix[i] = len;
	}
	return prefix;
}

void move_prefix(vector<int> &prefix) {
	for(int i=prefix.size() - 1; i > 0; i--)
		prefix[i] = prefix[i-1];	
	prefix[0] = -1;
}

int main() {
	[](){
		::ios::sync_with_stdio(false);
		cin.tie(0);
		cout.tie(0);
	}();
	string text,pattern;
	cin >> text >> pattern;
	vector<int> prefix = prefix_table(pattern);
	vector<int> backup(prefix);
	move_prefix(prefix);

	int n = pattern.length(),m = text.length();
	int i = 0,j = 0;
	// i+m配合.j+n配合
	while(i < m) {
		if (j == n-1 && pattern[j] == text[i]) {
			cout << (i - j + 1) << "\n"; 
			j = prefix[j];
		}
		// 开始模式匹配
		if (pattern[j] == text[i])
			i++,j++;
		else {
			j = prefix[j];
			if (j == -1)
				j++,i++;
		}
	}	
	for_each(backup.begin(),backup.end(),[](int &val){
				cout << val << " ";
			});
	return 0;
}