串的模式匹配算法：

BF算法：

依次比对pattern与滑动窗口中的对应位置上的字符；比对完成后将滑动窗口向右移动1位，直到找完全部的所需匹配。
时间复杂度：O(M * N)

KR算法：

将滑动窗口内m个字符的比较转化为哈希值的比较：仅当滑动窗口内的哈希值相等时，再一一比较窗口内的字串是否相等。

哈希算法：

KR算法的效率主要取决于哈希函数的选取。
滑动窗口的哈希值计算公式为：

当滑动窗口右移时，重新计算窗口的哈希值得到：

a为即将滑出窗口的字符；b为即将滑入窗口的字符。

KMP算法：

KMP的使用目的，及优势：

目的：
KMP是一种高效的字符串匹配方法。

比较优势：
1，当我们使用朴素的暴力枚举算法找到相同字符串位置的思路：

逐个枚举主串的每一个字符，作为匹配模式串的起始字符，然后将两字符串从起始位置开始逐个比较，若遇到不匹配位置，则将主串的起始比较位置移动到下一个字符重新开始。直到模式串枚举完，或是主串结束仍为找到匹配位置为止。

2，KMP算法的改进优化：

它主要改变了主串索引 i 的移动方式：

利用了匹配失败前部分匹配成功的信息，保证主串的指针i不回溯，通过修改模式串的指针j，是模式串尽量移动到有效的匹配位置。

由图可知，我们每次是将模式串移动到最大匹配位置。

那么什么是最大匹配位置？即满足以下几个条件：

· 每次重新匹配时，匹配的均是模式串的前缀

· 匹配失败时，j前重叠部分为主串的后缀

· 若要移动至最大匹配部分，即为满足前缀 = 后缀部分。

因此问题转化为了求模式串在每个字符位置处，以该字符结尾的最大相等前缀和后缀长度，以next数组存储，同时next数组还指引了每次回溯时模式串的回溯位置。

解释next数组各参数的含义：

· next[i] 参照的对象是模式串中p[ 1 ~~ i ]这部分子串；

· next[ i ] = j 表示在模式串 p[ 1 ~~ i ] 这个范围内，子串（前缀）p[ 1 ~~ j ]

与子串（后缀) p[ i - j + 1] 相等，且为最长前后缀。

next数组构造过程：

构造代码如下：

int ne[10010] = {0};
   char p[10010], s[10010];
   cin>>n>>p+1>>m>>s+1;  //下标从1开始。p为模式串，s为模版串，n m分别为其长度
   for(int i = 2, j = 0; i <= n; ++i){
    while(j && p[i] != p[j+1]) j = ne[j];  //回溯。j为0退无可退
    if(p[i] == p[j+1]) j++;
    ne[i] = j;
   }

KMP匹配过程：

过程与思路与上述类似，故不再赘述

for(int i = 1, j = 0; i <= m; ++i){  //检索原串
    while(j && s[i] != p[j+1]) j = ne[j];
    if(s[i] == p[j+1]) j++;
    if(j == n){  //模式串已完全匹配
        cout<< i - n <<" ";
        j = ne[j]; //为下次匹配做准备
    }
   }

故整体代码为：

#include<bits/stdc++.h>
using namespace std;
const int N =10010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{
   cin>>n>>p+1>>m>>s+1;

   for(int i = 2, j = 0; i <= n;++i){
    while(j && p[i] != p[j+1]) j = ne[j];
    if(p[i] == p[j+1]) j++;
    ne[i] = j;
   }

   for(int i = 1, j = 0; i <= m; ++i){
    while(j && s[i] != p[j+1]) j = ne[j];
    if(s[i] == p[j+1]) j++;
    if(j == n){
        cout<< i - n<<" ";  //输出匹配位置
        j = ne[j];
    }
   }
   return 0;
}