KMP字符串

题目描述

给定一个字符串 S，以及一个模式串 P ，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N，表示字符串 P的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S的长度。
第四行输入字符串 S。
输出格式
共一行，输出所有出现位置的起始下标（下标从 0
开始计数），整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例：
3
aba
5
ababa
输出样例：
0 2

通过阅读题目描述，我们可以迅速打出一个暴力代码

#include <iostream>
using namespace std;
const int N = 1000010;
string p, s;
int n,m;
int ne[N];
int main() {
    cin >> n >> p >> m >> s;
    for(int i = 0; i < s.size(); i ++){
        bool f = true;
        for(int j = 0; j < p.size(); j ++){
            if(s[j + i] != p[j]) {
                f = false;
                break;
            }
        }
        if(f) cout << i << ' ';
    }
    return 0;
}

可是我们看看数据范围
$1≤N≤10^5$
$1≤M≤10^6$
一看就不能使用暴力来写。
于是，我们就可以使用KMP算法来写
先介绍下什么是KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

了解了KMP算法是什么之后，我们就要想：如何解决这个题呢？
这里就要引入前后缀的概念了。

知道这个之后，我们就要开始进行具体的过程了

先求出如果不匹配，需要回退到哪里
在进行判断

代码

#include <bits/stdc++.h>
using namespace std;
int ne[1000005],n,m;
string p,s;
int main(){
    cin >> n >> p >> m >> s;//读入
    for(int i = 2,j = 0; i < p.size() + 1; i ++){
        while(j && p[i - 1] != p[j]) j = ne[j];//一直回退
        if(p[i - 1] == p[j]) j ++;//如果i - 1与j所表示的字母相同时，j向前进
        ne[i] = j;//放入next数组
    }
    for(int i = 0,j = 0; i < s.size(); i ++){
        while(j && s[i] != p[j]) j = ne[j];
        if(s[i] == p[j]) j ++;
        if(j == p.size()){//如果判断到了模版串末尾
            cout << i - j + 1 << ' ';//输出答案
        }
    }
    return 0;
}