// 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;
        }
    }
}

如何优化

nect[i]：以i为起点的后缀和开头的某部分前缀相等且为长度最大
需要p[1, j] = p[i-j+1, i]这两段是相等的
求next数组：

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){
        cout << i - n << ' ';
        j = ne[j];
    }
}