OI竞赛中，字符串匹配也是一个比较有趣的东西
一般地，字符串匹配问题通常给出原串(String)与模式串(Pattern)，要求输出模式串在原串中出现的起始位置。比如：
原串：abacaba
模式串：aca
答案就是3
今天我们来讨论只有两个串的情况（就是没有trie和AC自动机QAQ）
对于这种问题，我们有好几种方法来解决
1.暴力
只需暴力枚举起始位置，然后暴力判断，复杂度O(n*m)。
这种方法对于随机数据一般没什么问题（随机数据匹配度很差）
但是很容易被手造数据卡掉：
原串：aaaaaaaaaaaaaaaaaaab
模式串：aaaaaab
2.字符串hash
这个东西相较于上面那个靠谱得多，但这里我们不细讲，粗略讲一下思路
我们给子串一个值，使得在判断两个字符串是否相同的时候，可以直接比较它们所对应的值，避免逐位比较。
做法是把每一位（ascll码或者随你便）相乘然后存hash，如果害怕有冲突可以多取几个hash函数
3.Kmp字符串匹配算法
今天的重头戏来啦
首先引入一个概念：border
在字符串S中，我们将能与S前缀匹配的S的后缀称之为border。
例如“ABABAB”的border集合是{2,4,6}。
意思就是说呢，在串s中，s[1~i]和s[len-i+1~len]两部分的串是相同的，我们就把i看成是串s的一个border
这个东西有什么用呢？接着往下看
一般的暴力做法，如果s1[i+j]与s2[j]不匹配，就直接抛弃前面的j-1个匹配的子串从s1[i+1]与s2[1]重新开始匹配，那不是有浪费？
显然前s1[i~i+j-1]和s2[1~j-1]是匹配的对吧，那么Kmp算法便保留了这已经匹配好的一部分作为下次备用
这样时间是不是降下来了？
我们要改变的只是这个j，要使它能够满足原串与模式串的匹配而且最大
那么border就派上用场了 
（——by xxy orz）
从上面两张图中可以看出，当i匹配到第六位时，匹配失败，于是我们找到了刚才已经匹配成功的部分，也就是b串的前面5位
我们发现,b[1~3]和b[3~5]是一样的，即b[1~5]的border是3
那么我们就可以把b串前移，这是可以匹配的是不是？
我们可以设一个数组nex，表示当匹配到B数组的第i个字母而第i+1个字母不能匹配了时，前移最大是多少。
nex[i]应该是所有满足b[1..nex[i]] = b[i-nex[i]+1..i]的最大值。(即，最大的border长度)
这个东西是可以预处理出来的
int j=0;
for(int i=2;i<=l2;i++){
while(j&&b[i]!=b[j+1])j=nex[j];
if(b[i]==b[j+1])j++;
nex[i]=j;
}匹配子串的时候遇到不能匹配的情况时，将j退到nex[j]，如若还是不能匹配，再退……直到不能再退（也就是到头了）或者可以匹配为止，然后把当前位置nex赋值为j就好啦
如果完全匹配就是答案啦
j=0;
for(int i=1;i<=l1;i++){
while(j&&a[i]!=b[j+1])j=nex[j];
if(a[i]==b[j+1])j++;
if(j==l2)printf("%d\n",i-l2+1),j=nex[j];
}感觉代码很短的样子是不是？（我感觉比hash还短）
我们来分析一下时间：
若匹配，则j->j+1，花费时间O(1)。
若不匹配，则j->nxt[j]，那么将nxt[j]再次增长到j需要付出O(j-nxt[j])的时间，会摊给以后的匹配，实质复杂度依然是O(1)的。
所以这个东西的时间复杂度降下了一个档次：O(n+m)近似于O(n)
下面就是模板啦！
模板题：LuoguP3375 https://www.luogu.org/problem/show?pid=3375
这很模板，直接上面两个代码拼起来就解决了
#include<bits/stdc++.h>
using namespace std;
int nex[1000001],l1,l2;
char a[1000001],b[1000001];
int main()
{
scanf("%s",a+1);
scanf("%s",b+1);
l1=strlen(a+1);l2=strlen(b+1);
int j=0;
for(int i=2;i<=l2;i++){
while(j&&b[i]!=b[j+1])j=nex[j];
if(b[i]==b[j+1])j++;
nex[i]=j;
}
j=0;
for(int i=1;i<=l1;i++){
while(j&&a[i]!=b[j+1])j=nex[j];
if(a[i]==b[j+1])j++;
if(j==l2)printf("%d\n",i-l2+1),j=nex[j];
}
for(int i=1;i<=l2;i++)printf("%d ",nex[i]);
}其它相关算法题目我会另写题解
参考：xxyPPT