title: kmp算法
tags: ACMer
categories: String
thumbnail: https://gss3.bdstatic.com/84oSdTum2Q5BphGlnYG/timg?wapp&quality=80&size=b150_150&subsize=20480&cut_x=0&cut_w=0&cut_y=0&cut_h=0&sec=1369815402&srctrace&di=0af3d14b50480593f373e4a71dda5c97&wh_rate=null&src=http%3A%2F%2Fimgsrc.baidu.com%2Fforum%2Fpic%2Fitem%2Fca1349540923dd540360d836d209b3de9c824858.jpg

什么是kmp算法

快速地从某一个主串找到一个模式串

暴力匹配算法

S[N], p[M]
    // 0, 1 都行
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算法

原来做法的特点：我们在找移动的时候太缓慢了。我们应该有更加快速的移动方式

即，有些额外信息是可以共用的。

假设：

next[i] := p串中后缀和前缀相等，且长度最长的量

即，p[1, j] == p[i - j + 1, i]

我们怎么找next数组呢？

1. 预处理的思想
2. 其实是拿自己的串比较自己
3. 如果某一个位置不相等就移到某个位置
4. 如果相等了就再加
5. 然后让当前位置的next[i] = j

#include <bits/stdc++.h>

using namespace std;
const int maxn  = 1e5 + 10;
char p[maxn], s[maxn];
int n, m;
int ne[maxn];  // 命名为ne，因为next可能是某个头文件的

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;  // 这里对尾地址进行处理了
    
    // 寻找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;
    }
    
    
    // kmp匹配过程
    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 + 1 - 1);
            j = ne[j];
        }
    }
}

KMP算法

原文：https://www.cnblogs.com/WalterJ726/p/12459542.html