kmp板子

书上讲的感觉不好理解，不如算法竞赛上分析的

题目链接：
https://www.luogu.com.cn/problem/P3375
贴板子：

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;


const int N = 1e6 + 5;
string tar, p;
int Next[N];
queue<int>qid;

void getNext()
{
	Next[0] = Next[1] = 0;
	for (int i = 1; i < p.length(); i++)
	{
		int j = Next[i];
		while (j and p[i] != p[j])j = Next[j];//回退
		if (p[j] == p[i])Next[i + 1] = j + 1;//修改i+1等于j+1（指向的位置）
		else Next[j + 1] = 0;//回退到id=0
	}
}
void kmp()
{
	getNext();//预处理Next数组
	int j = 0;
	for (int i = 0; i < tar.length(); i++)
	{
		while (j and tar[i] != p[j])j = Next[j];
		if (tar[i] == p[j])j++;
		if (j == p.length()) { qid.push(i - p.length() + 1 + 1); j = Next[j ]; }//qid的push这里要注意下就行，根据题目来
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> tar >> p;
	kmp();
	while (!qid.empty())
	{
		cout << qid.front() << endl;
		qid.pop();
	}
	for (int i = 1; i < p.length(); i++)cout << Next[i] << ' ';
	cout << Next[p.length()];
	return 0;
}