题目描述

给定s,p判断p是否是s子串

算法1

(暴力枚举) $O(nm)$

算法2

(kmp) $O(n+m)$

kmp下标从1开始的话容易思考些。

先理解匹配数组

ababa的前缀为a,ab,aba,abab， 后缀为 a, ba, aba, baba, 前后缀都不包含自身

那么匹配数组ne[1..5]为 0 0 1 2 3

ne[1] = 0表示没有前后缀（因为前后缀不包含自身）

那么s[i] != p[j+1] 时,令k=ne[j] ,k就是最长前缀=后缀长度
由匹配数组ne的含义可知 p[1..k] = p[j-k+1..j]

暴力做法从头枚举相当于p往右移动了1位，这样相当于p往右移动了多位，效率自然提升上来了。

求ne数组：
假设ne[1 ~ i-1]已经求出, ne[i]的候选项只可能在ne[i-1], ne[ne[i-1]], ne[ne[ne[i-1]]] 里面选，假设候选项=k
且p[i ] == p[k+1]的话， ne[i] = k + 1,这个定理证明书籍上有

C++ 代码

#include <iostream>

using namespace std;
const int M=100010;
char s[M], p[M];
int ne[M];
int main(){
    int n, m, j, i;
    cin>>n>>p+1;
    cin>>m>>s+1;
    for (i = 2, j = 0; i <= n; i ++){
        while (j && p[j+1] != p[i]) j = ne[j];
        if (p[j+1]==p[i]) j++;
        ne[i] = j;
    }
    for (i = 1, j = 0; i <= m; i ++){
        while(j && p[j+1]!=s[i]) j = ne[j];
        if (p[j+1] == s[i]) j++;
        if (j == n) {
            cout<<i-j<<" ";
            j = ne[j];
        }
    }
    return 0;

算法3

(kmp 有限自动机版本) $O(m+n)$

x存储跟当前状态前后缀相同的最长子串所位于的状态
显然,只有p串前后缀相同时，枚举下一个状态，x才能往后跳动到长度更长的状态，可以模拟一遍就理解了这种神奇的方式为啥能保证x是前后缀相同的最长的前缀所处的状态

#include <iostream>
using namespace std;

const int C = 1e5 + 5;
string s, p;
int n, m;
int dfa[C][123];

int main(){
    cin >> n >> p >> m >> s;
    dfa[0][p[0]] = 1;
    int x = 0;
    for (int i = 1; i < n; i ++) {
        for (int j = 0; j < 123; j ++) dfa[i][j] = dfa[x][j];
        dfa[i][p[i]] = i + 1;
        x = dfa[x][p[i]];
    }
    int j = 0;
    for (int i = 0; i < m; i ++) {
        j = dfa[j][s[i]];
        if (j == n) {
            cout << i-j+1 << " ";
            j = x;
        }
    }
    return 0;
}