初探KMP算法

算法简述

KMP是单模匹配算法，在一个长度为n的文本串中查找一个长度为m的模式串。它的时间复杂度是O(m+n)，是这类算法的理论最优复杂度。
模式匹配：在长为n的字符串S中，找到某个长为m的模式串P，复杂度至少是O(m+n)。

1. 朴素的模式匹配算法

普通的暴力方法是从S中逐个字符开始匹配P中每个字符。最好复杂度是O(m+n),例如S = "abcdefg123", P = "123"，只需处理7+3=10次。最差复杂度是O(mn)，例如S = "aaaaaaab" ,P = "aab",要匹配5*3+3=18次。

2. KMP算法

KMP是在任何时候都能达到O(m+n)复杂度的算法。它通过预处理P，使得在与S匹配时能够跳过一些字符，达到快速匹配的目的。

算法原理

KMP中，在比较S[i]，P[j]时，i指针会走到S串尾不回溯，而只回溯j指针达到快速匹配目的，其是通过KMP的核心next[]数组做到，回溯时next[]数组会给出j回溯的位置。

1. next数组

next[i+1] = P[i]之前(包括i)相同前后缀的最大长度，从而做到在S[i+1]!=P[j]后回溯时，通过j = next[j]就可以回到P[j-1]之前(包括j-1)相同前后缀的前缀末端+1的位置开始匹配。
我们可以通过如下代码得到next[]数组，复杂度为O(m)：

void getNext(char *p,int plen){
    Next[0] = -1;
    for(int i = 0;i

int kmp(char *s,char *p){
    int cnt = 0;
    int slen = strlen(s);
    int plen = strlen(p);
    getNext(p,plen);
    int j = 0;
    for(int i = 0;i

#include 
#define TLE std::ios::sync_with_stdio(0),cout.tie(0),cin.tie(0)

using namespace std;

char s[1010],p[1010];
int Next[1010];
int ans[1010];


void getNext(char *p,int plen){
    Next[0] = -1;
    for(int i = 0;i>s>>p;
    int cnt = kmp(s,p);
    cout<