实现strstr（）

实现strstr（）

 这题为kmp算法

字符串的匹配

我们现在先不看这道题，来看看kmp是怎么实现的

kmp实现有两个重要步骤

1.实现next数组，也就是最长相等的前后缀长度

2.字符串的匹配

 

 我们现在通过代码直接来讲解思路，因为直接将，可能比较抽象

步骤：

1.n，m分别为模式串和模板串的长度

2.ne[N]为next数组

3。为什么读入字符串的时候从1开始读入，这里是为了方便next数组的求出，如果从零开始，那么之后每个next数组的下标还要集体往后退一步，不如直接从1开始读入

4.第一个循环为求next数组，第二个循环为字符串匹配的过程

我们先从字符串匹配的过程讲起，也就是从第二个循环开始讲起

字符串是如何匹配的呢，以及没有成功，最少要退多少位

注意：这里为什么j从0开始，不是从1开始读入的吗

这里我们可以看看

这是字符串匹配的过程，我们是对i和j+1所指向的值进行比较

之后如果i和j+1的值不匹配，那么j所指向的next数组的值就是已经匹配的字符串最长相同前缀后缀

最长相同前缀后缀怎么求

以上图p为例

abababab

a，0

ab ，0

aba，a，1

abab，ab，2。。。。。

while(j)为什么要判断j不等于0，因为当j=0，表示还一个字符串都没匹配

如果相等j++，不相等，就根据next数组退一定的位数

如果等于m相当于匹配完成，

求next数组的 *** 作和字符串匹配的 *** 作差不多，就是把相同的模板串p作比较

如果不相等就回去用next数组退回去，匹配j++，然后记录一下匹配的字符串数目，也就是求next数组，这里为什么i从二开始，因为next【1】都为0，不用 *** 作

步骤：

1.从1开始读入字符串

2.求next数组，自己和自己比，从1开始存入

i从2开始因为next【1】本来等于0 不需要再做，特判j=0，一个字符都没有匹配

3.字符串匹配，模式串和模板串比i从1，开始，

如果相等j++，否则j=ne【j】

#include 

using namespace std;

const int N = 100010, M = 1000010;

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

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    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)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

因为最后答案是从0开始读入的，所以是i-n。