KMP

暴力算法怎么做

S[N], p[M]
for(int i=1;i<=n;i++)
{
    bool flag=true;
    for(int j=1;j<=m;j++)
    {
        if(s[i+j-1]!=p[j])
        {
            flag=false;
            break;
        }
    }
}

KMP字符串题目链接

831. KMP字符串 - AcWing题库

KMP字符串题目类型

KMP

KMP字符串代码

#include<iostream>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    cin >> n >> p+1 >> m >> s+1;
    // 求ne的过程，相当于求前缀子串和后缀字串的最大共同字串长度
    // 样例 假设p为ababaaba
    // ne[1]=0  默认为0
    // ne[2]=0  a!=b
    // ne[3]=1  a
    // ne[4]=2  ab
    // ne[5]=3  aba
    // ne[6]=1  a
    // ne[7]=2  ab
    // ne[8]=3  abc
    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)
        {
            printf("%d ",i-n);
            j = ne[j];
            // 匹配成功
        }
    }
}