【21. KMP算法】

解决问题

KMP能解决字符串匹配。
在文本串中是否出现模式串。

BF算法（暴力破解）

思路：

• 俩个指针 i， j 分别指向文本串和模式串，当模式串字符与文本串字符，不一样时，此时需要将模式串向后移动一位。

代码

int bt(string str, string pattern)
{
    int len1 = str.length();
    
    int len2 = pattern.length();
    for (int i = 0; i < len1 ; i ++)
    {   
        int j = 0;
        for (; j < len2; j ++ )
        {
            if (str[i + j] != pattern[j])
            {
                break;  //如果不相等，直接跳出循环，j从头开始
            }
           
        }
         if (j == len2 ) return i;
    }
    return -1;
} 

KMP算法：

思路：

• 因为BF算法是一位一位的比较，所以时间复杂度比较高，KMP是通过减少比较次数，来进行优化.
• BF是匹配不成功只移动一位，而KMP算法匹配不成功，移动多位，具体移动几位，需要查前缀表。

前缀表与后缀表

• 当遇到不匹配时，就需要找前面一个数的最长相等前后缀是多少，然后再跳到该地方，继续与文本串进行比较。

前缀：包含首字母，不包含尾字母的所有子串。

后缀：不包含首字母，包含尾字母的所有子串。

模式串 a b a a b。

• 前缀有 a ab aba abaa.
• 后缀有 b ab aab baab 。

最长相等前后缀
a：没有相等前后缀只有本身next[0] = 0
aa:前缀a, 后缀a，相等前后缀长度是1. next[1] = 1
aab:没有相等前后缀next[2] = 0
aaba:前缀a, 后缀a，相等前后缀长度是1. next[3] = 1
aabaa:前缀aa, 后缀aa，相等前后缀长度是2. next[4] = 2
aabaaf:没有相等前后缀next[5] = 0

next[]所组成的0, 1 , 0 , 2, 0 , 0 就是前缀表

next数组(也就是前缀表)

next数组为什么 j = next[j - 1],而不是j = next[j];

next数组的性质：

• P[0] 到 P[i] 这一段子串中，前next[i]个字符与后next[i]个字符一模一样。
• 我们可以拿长度为 next[r-1] 的那一段前缀，来顶替当前后缀的位置，让匹配继续下去

匹配例子：

• P[4]失配后，把P[next[3-1]]也就是P[1]对准了主串刚刚失配的那一位；P[6]失配后，把P[next[6-1]]也就是P[3]对准了主串刚刚失配的那一位。

题目

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串 P 在模式串 S 中多次作为子串出现。

求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤ N ≤ 105
1≤ M ≤ 106

输入样例：

3
aba
5
ababa

输出样例：

0 2

代码

#include <iostream>
#include <string>
using namespace std;

int n, m;
const int N = 100010, M = 1000010;

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

int main()
{
    cin >> n >> p  >> m >> s ;
    for (int i = 1,  j = 0; i < n; i ++)
    {
        while (j && p[i] != p[j ]) j = ne[j-1] ;
        if (p[i] == p[j ]) j ++;
        ne[i ] = j ;
    }
    
    for (int i = 0, j = 0; i < m; i ++)
    {
        while (j && s[i] != p[j ])  j = ne[j-1];
        if (s[i] == p[j ]) j ++;
        if (j == n)
        {
            printf("%d ", i - j + 1);
            j = ne[j-1];
        }
    }
    return 0;
    
}

可以参考https://www.zhihu.com/question/21923021/answer/1032665486