字符串算法很有趣，尤其是KMP和AC自动机~~

大纲

1.问题定义

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。例如，ATCTAGAGA是字母表∑ = {A,C,G,T}上的一个字符串。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上。

还是比较好理解的，这段就过了吧

2.实现

1.朴素

俗话说，暴力出奇迹。这种匹配问题给人的第一直觉就是用暴力，一个个比嘛，不匹配就换下一个呗

char T[maxn],P[maxn]
void check()
{
	int lenT=stren(T);
	int lenP=strlen(P);
	int i = 0; // 主串的位置
    int j = 0; // 模式串的位置
	while (i < t.length && j < p.length) 
	{
          if (t[i] == p[j]) { i++;j++;} 
          else 
          {
          	i = i - j + 1; 
          	j = 0; 
          }
     }
		   if (j == p.length) return i - j;
           else return -1;
}
...

但是，这份代码与接下来要分析的KMP比起来，差了太多，因为它的时间复杂度太大

2.KMP

1.思想

假设现在有一主串T，一模式串P

当匹配到P的最后一个字符时发现失配了，那么上面那段暴力代码就会将P整体后移1位然后再重复

但不难发现，P中其实有我们可以利用的东西
P的第1，2位和失配的最后一位字符的前两位字符完全一样
既然我们已经把1~7位都匹配了一遍况且第1，2位和6，7位相等，这也就意味着T的6，7位和P的1，2位是等价的，于是就可以有下面的操作

可以用几个式子来概括当T[i]与P[j]失配时，可以直接将P向后移动k个位置而不用依次比较的原因（来自https://www.cnblogs.com/yjiyjige/p/3263858.html）

$当T[i] != P[j]时$

$有T[i-j 到 i-1] == P[0 到 j-1]$

$由P[0 到k-1] == P[j-k 到j-1]$

$必然：T[i-k 到i-1] == P[0 到k-1]$

这就是它的思想，不做无用功~~

流程（以luogu3375为例）

nxt数组

上文已经提到过，当失配时，我们不需要像暴力代码一样一个个跳，而是可以通过“智慧的手段”来减少工作量。而这个“智慧的手段”是什么?其实就是大名鼎鼎的next数组（为了避免关键字重名，一般使用nxt）
什么是nxt数组？
nxt[i]就是指模式串中以第i-1项结尾的字符串的最长公共真前后缀的长度，其性质是 $P[1->nxt[i]]==P[strlen(p)-nxt[i]]->i-1]$
nxt数组的作用
细心一点就可以看出来，上式中的nxt[i]就是上文里讲到的k（移动的位数）

因此当失配时，直接让失配时的指针跳nxt数组就好了

假设我们此时已经有了nxt数组，那么KMP的大致框架就出来了

#define clean(arry,num); memset(arry,num,sizeof(arry));
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i<=end;i--)
#define printarry(arry,size) for(int i=1;i<=size;i++)printf("%d ",arry[i]);
void KMP()
{
	int len1=strlen(s1);
	int len2=strlen(s2);
	int i=0;int j=0;
	while(i<len1)
	{
		if(j==len2-1&&s1[i]==s2[j])printf("%d\n",i-len2+2);
		if(j==-1||s1[i]==s2[j]){i++;j++;}
		else j=nxt[j];
	}
	printarry(nxt,len2);
}

如何求得nxt数组
现在我们离KMP就差一个nxt数组啦
先给出求nxt的代码，看看能看懂不

void getnxt()
{
	nxt[0]=-1;//初值
	int len=strlen(s2);//s2是模式串，就是P
	int j=-1;
	int i=0;
	while(i<len)
	{
		if(j==-1||s2[i]==s2[j]){nxt[++i]=++j;}
		else j=nxt[j];
	}
	return;
}

在这份代码中，我们用了i,j两个指针来维护nxt数组，外层的while是nxt的位数（从第0位枚举到最后一位），i就是外层的指针
然后的if…else是精华，它以j为指针，是为了维护i的nxt值，这其中包含了3种情况：
1.当j实际指向第1个字符时
2.当i,j所指的字符相同时
3.当i,j指向的字符不同时

第一种情况和第二种情况都比较好解决，直接就把i,j向后移一位，然后用j的值来更新nxt[i]（只要i,j所指的字符相同，那么其前面的字符也都相等），其在代码中就体现在

if(j==-1||s2[i]==s2[j]){nxt[++i]=++j;}

第三种情况实际上是一个递归，只是这个递归没有用函数调用的方式
当第三种情况出现时，可以肯定j以前的nxt都求出来了，而此时的s2[i]!=s2[j]，也就意味着s2的nxt[j]项可能与s2[i]相同，于是将j赋值nxt[j]，继续循环，此时，如果j仍然不满足要求，那就又继续赋值，直到找到符合要求的或是达到边界（j=-1）

这期间，j的值是从于i相差1一直减小，最小到-1的

这体现在

else j=nxt[j];

这就是KMP的大致框架，下面附上代码

#include<bits/stdc++.h>
using namespace std;
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i<=end;i--)
#define printarry(arry,size) for(int i=1;i<=size;i++)printf("%d ",arry[i]);
const int maxn=1000000+10;
char s2[maxn],s1[maxn];
int nxt[maxn];
void calcnxt()
{
	int len=strlen(s2);
	int j=-1;
	int i=0;
	while(i<len)
	{
		if(/*j<=1*/j==-1||s2[i]==s2[j]){nxt[++i]=++j;}
		else j=nxt[j];
	}
	return;
}
void KMP()
{
	int len1=strlen(s1);
	int len2=strlen(s2);
	int i=0;int j=0;
	while(i<len1)
	{
		if(j==len2-1&&s1[i]==s2[j])
		{
			printf("%d\n",i-len2+2);//
		}
		if(j==-1||s1[i]==s2[j]){i++;j++;}
		else j=nxt[j];
	}
	printarry(nxt,len2);
}
int main()
{
   freopen("datain.txt","r",stdin);
   scanf("%s%s",s1,s2);
   clean(nxt,0);
   nxt[0]=-1;
   calcnxt();
   KMP();
   return 0;
}
/********************************************************************
   ID:Andrew_82
   LANG:C++
   PROG:KMP
********************************************************************/

~~感觉自己对这个算法的理解又加深了~~
本文的部分思路来自以下几个大佬的博客
孤~影
 北京小王子
若有不周之处，请多多指教

浅谈单模式串字符串匹配算法（KMP）

大纲