给出两个字符串 �1 和 �2，若 �1 的区间 [�,�] 子串与 �2 完全相同，则称 �2 在 �1 中出现了，其出现位置为 �。
现在请你求出 �2 在 �1 中所有出现的位置。

定义一个字符串 � 的 border 为 � 的一个非 � 本身的子串 �，满足 � 既是 � 的前缀，又是 � 的后缀。
对于 �2，你还需要求出对于其每个前缀 �′ 的最长 border �′ 的长度。

输入格式

第一行为一个字符串，即为 �1。
第二行为一个字符串，即为 �2。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 �2 在 �1 中出现的位置。
最后一行输出 |�2| 个整数，第 � 个整数表示 �2 的长度为 � 的前缀的最长 border 长度。

输入输出样例 #1

输入 #1

ABABABC
ABA

输出 #1

1
3
0 0 1 

说明/提示

样例 1 解释

。

对于 �2 长度为 3 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1。

数据规模与约定

本题采用多测试点捆绑测试，共有 4 个子任务。

• Subtask 0（30 points）：|�1|≤15，|�2|≤5。
• Subtask 1（40 points）：|�1|≤104，|�2|≤102。
• Subtask 2（30 points）：无特殊约定。
• Subtask 3（0 points）：Hack。

对于全部的测试点，保证 1≤|�1|,|�2|≤106，�1,�2 中均只含大写英文字母。

P3375 【模板】KMP

---

这题有好多讲法，我的不一定清楚，尽量讲吧

什么是KMP算法？

---

所谓的KMP，就是在主串中快速地找出模式串的位置
这里我们需要一个fail数组，其中fail[i]的意思是模式串前i个字符的前缀的最长公共前后缀
接下来我会拿图来解释：
 

此时开始遍历每一个字符，直到......

下一个字符不匹配！！！！！
那咋办？
如果从头开始重新遍历，时间复杂度将会大爆炸......
那有没有更快的方法？有的，就是KMP：
由于fail数组存的是模式串的前i个字符组成的前缀的最长公共前后缀，
那么拿此图来讲，模式串中字符d的前面肯定是跟主串一样，
 

那么显然的，红色部分与黄色部分是完全相等的，此时我们就可以偷懒了，
将指针j调到fail[j]继续匹配。

为什么跳到fail[j]？

---

fail[j]表示的是最长公共前后缀，就是红色部分的长度！！
所以我们的指针跳到fail[j]，
 

注：也可以理解为讲模式串的第fail[j]位跳到j的位置:
 

那么一直遍历到结束......
 

发现所有都符合，于是我们找到了答案。

题目解析

---

此题目中的border就是fail数组的每个值（不解释）
所以我们在进行查找过后，直接输出fail数组的值就好了
其他的依照上述的KMP讲解写就好了
绝对不是我懒得写解析

ACcode:

---

//其实解析在这里(doge)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int f[N];//f[i]：模式串t的前i-1个字符的最长相同前后缀长度
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s,t;
	cin>>s>>t;
	for(int i=2;i<=t.size();i++)//i:模式串位置
	{
		int j=f[i-1];//j:上一个位置的最长相同前后缀长度
		while(j and t[j]!=t[i-1]) j=f[j];//如果不匹配，就继续往前找，直到找到匹配的或者j=0
		if(t[j]==t[i-1]) j++;//匹配则长度加1
		f[i]=j;//记录当前位置的最长相同前后缀长度
	}
	for(int i=0,j=0;i<s.size();i++)//i:主串位置，j:模式串位置
	{
		while(j and s[i]!=t[j]) j=f[j];//如果不匹配，就继续往前找，直到找到匹配的或者j=0
		if(s[i]==t[j]) j++;//匹配则模式串位置加1
		if(j==t.size())//找到了一个匹配
		{
			cout<<i-j+2<<endl;//输出匹配位置，注意下标从1开始
			// 注：假装失配继续找下一处
			j=f[j];//为什么要假装失配？因为可能存在重叠匹配，这样可以从最优(匹配最长)的位置继续匹配
		}
	}
	for(int i=1;i<=t.size();i++) cout<<f[i]<<" "; //依照题意输出
	return 0;
}
//Author:AAA_jiancaipifa