题前的废话：
中考结束了呀
他们都放假了呀
我在学校学习了呀
真好呀
感觉我超废
首先，我们需要知道KMP算法是干嘛的呀：
KMP算法是用来处理字符串匹配问题的；
字符串A=“somebody ak ioi”，字符串B=“ioi”，最暴力的算法O(nm)直接暴力扫描，对于比较小的数据范围还可以，但是要是数据范围一大 (╯°Д°)╯︵┻━┻（直接掀桌）
所以我们就需要一些字符串算法来解决这个问题，比如KMP
KMP的工作思路：
- 用两个指针i和j，分别表示A[i-j+1~i]（被匹配串）与B[1~j]（匹配串）完全相同，这时如果A[i+1]与B[j+1]不相同，对于KMP算法，是考虑减小j的值（假设j=>k（方便写qwq）），使得A[i-k+1~k]与B[1~k]完全相同（并且使k尽量的大）
-
举个栗子：（哦对了，KMP算法好像要求字符串从1开始存储可以scanf("%s",a+1)这样存储）
- A=“abababaababacb” ；B=“ababacb”；
- 当i=5，j=5时：
-
（找到的新j） - 这时前5个时完全匹配的，但是天公不作美，第六个并不匹配，因此我们要考虑更换另一个数j（用k存着好写），因为更换以后A[i-k+1~k]与B[1~k]完全相同，而k<j，因此也就是B串的前k个与A串的从i向前数后k完全相同，因为我们知道B[1~j]与A[i-j+1~i]是完全相同的，因此 i-k+1~i其实是相当于（i-j+1+x~i）取i向前数的k个数与B[1~k]相同，又知道A[i-k+1~i]=A[i-k+1~i]=B[j-k+1,j]也就是说新选的这个j的B串的前j个与后j个完全相同，因此可以判定对于新选择的j只与B串有关，所以可以提前预处理：
- 对于预处理的方法，我觉得是只可意会不可言传的，但是我还是想写一写，要不然以后连意会都不行啦
-
举个栗子：
W ：a b a b a c b
p：0 0 1 2 ？？
假如我们有一个串，并且已经知道了p[1~4]那么如何求p[5]和p[6]呢？
我们发现，由于p[4]=2，所以w[1~2]=w[3~4]，求p[5]的时候，我们发现w[3]=w[5]，也就是说我们可以在原来的基础上+1，从而得到更长的相同前后缀，此时p[5]=p[4]+1=3
W ：a b a b a c b
p：0 0 1 2 3？
那么p[6]是否也是p[5]+1呢？显然不是，因为w[p[5]+1]!=w[6]，那么此时我们可以考虑退一步，看看p[6]是否可以由p[5]的情况所包含的子串得到，即是否p[6]=p[p[5]]+1？
事实上，这样一直推下去也不行，于是我们知道p[6]=0；
- 尽管我并没有讲明白，但是可以感性理解一下:
- 以下是预处理的代码：
void ych(){ p[1]=0; int f=0; for(int i=1;i<len2;++i){ while(f>0&&s2[f+1]!=s2[i+1]) f=p[f]; if(s2[f+1]==s2[i+1]) ++f; p[i+1]=f; } }
- 然后就可以写KMP算法啦：
-
void kmp(){ int j=0; for(int i=0;i<len1;i++){ while(j>0&&s2[j+1]!=s1[i+1]) j=p[j]; if(s2[j+1]==s1[i+1]) j++; if(j==len2){ printf("%d ",i+1-len2+1); j=p[j]; } } }
看一个板子题【洛谷p3375】KMP字符串匹配
很简单的板子题，完完全全的KMP，就楼上两步代码合起来然后输入输出再搞一搞就好啦；
CODE：
#include<bits/stdc++.h> using namespace std; char s1[1000010],s2[1000010]; int p[1000010],len1,len2; void ych(){ p[1]=0; int f=0; for(int i=1;i<len2;++i){ while(f>0&&s2[f+1]!=s2[i+1]) f=p[f]; if(s2[f+1]==s2[i+1]) ++f; p[i+1]=f; } } void kmp(){ int j=0; for(int i=0;i<len1;i++){ while(j>0&&s2[j+1]!=s1[i+1]) j=p[j]; if(s2[j+1]==s1[i+1]) j++; if(j==len2){ printf("%d ",i+1-len2+1); j=p[j]; } } } int main(){ scanf("%s",s1+1); scanf("%s",s2+1); len2=strlen(s2+1); len1=strlen(s1+1); ych(); kmp(); for(int i=1;i<=len2;i++) cout<<p[i]<<" "; return 0; }