KMP与字符串哈希

1. KMP

在字符串匹配问题中，假设有母串 S : s1,s2,s3,s4,...，现有子串 T : t1,t2,t3,...，问子串 T在母串中存在得次数。

暴力解法

从母串 S 开始，一个一个字符进行匹配， i从 0 开始， j从 i到子串 T长度匹配，具体暴力解法如图所示

从时间复杂度来看，若 S长度为 n， T长度为 m ，则$O(n*m)$ ，当然这样子可以求子串数量，也可以求子串在母串中的位置等等。

暴力解法C++代码：

    int ans=  0;
    for(int i = 1;i <= n;i++){
        bool flag = true;
        for(int j = 1;j <= m;j++){
            if(s[i + j - 1] != t[j]){
                flag == false;
                break;
            }
        }
        if(flag){
            ans++;
        }
    }

KMP解法

在以上的分析中我们已经直到暴力解法不可行，母串下标 i不可以直接 i++，而是通过某一种手段进行步长的增加。

KMP

KMP在已经匹配的 s[j] 中寻找最长的相同前后缀，前后缀相同且已经与 s[i] 匹配，那么拿出最长的后缀位置作为 i 的跳转下标。

首先我们要对已经匹配的s[j]中计算最长前后缀，其实也就是s[j]的最长前后缀，

//1、求next数组，即t的最长前后缀
    //j 表示已经匹配成功的下标 ， i表示q数组中的下标
    for(int i = 2, j = 0;i <= m;i++){
        //q数组从1开始，所以i == 1 为0
        while(j && p[i] != p[j + 1]){
            // 不匹配 
            j = ne[j];
        }
        //匹配
        if(p[i] == p[j + 1]){
            j++;
        }
        ne[i] = j;
    }

    //2、kmp匹配
    //j 表示匹配成功的长度
    for(int i = 1,j == 0;i <= n;i++){
        //如果不匹配跳转到ne[j]
        while(j && s[i] != p[j + 1]){
            j = ne[j];
        }

        //匹配成功j+1
        if(s[i] == p[j + 1]){
            j++;
        }

        if(j == n){
            //p匹配成功
            printf("%d ",i - j);
            j = ne[j];
        }
    }

2. 字符串哈希