KMP 算法

1. 暴力算法

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

2. KMP 算法

#include<iostream>
using namespace std;
const int N = 10010, M = 100010;
char p[N], s[M];
int nxt[N];
int n, m;


int main()
{
    cin >> n >> p+1 >> m >> s+1;
    
    // １. 构建　nxt 数组
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && p[i] != p[j+1]) j = nxt[j];
        if(p[i] == p[j+1]) j++;
        nxt[i] = j;
    }
    
    // 2. KMP 
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && s[i] != p[j+1]) j = nxt[j];
        if(s[i] == p[j+1]) j++;
        
        if(j == n)
        {
            printf("%d ", i-n);
            j = nxt[j];
        }
    }
    return 0;
}