【KMP字符串匹配算法】自留用学习

这个算法经常忘记，今天看了记录一下心得,自留用。

讲得比较好的:
字符串匹配算法KMP详细解释——深入理解
讲的比较详细的：
字符串匹配KMP算法的理解（详细）
简洁易懂版本：
转载一篇单字符串匹配KMP算法最好理解的文章

思路：

一般都先讲暴力匹配，这种情况下，每次都从字符串开头开始匹配，当子串长M，父串长N，复杂度是O(M*N)

匹配串的时候，例如：ABCDABD,每次都从头开始匹配，每次都要回溯子串到最初，这样没有利用已经匹配上的信息，例如：匹配到第二个B时失配，我们知道父串前面有ABCDA，所以如果从头开始匹配，可以直接从B开始匹配，因为知道前面已经有一个A了。 这样就利用了已知信息。
为了得到这样的信息，需要生成下面的next表。

A从子串首字符开始匹配，B从第二个字符开始匹配，其他的由于没有重复的结构，只能从头暴力匹配了。

如何生成next表：

从上面的描述我们知道，next表生成只与子串相关，与父串没关系。

如何使用next表：

用i，j标识父串和子串目前匹配到的位置，
现在每次需要回溯的距离=目前子串匹配到位置-next[i]

例如：BBC  ABCDAB  ABCD  
          ABCDABD

此时匹配到D，不匹配了，则 i=i+4 且 j=2。

例如：BBC  ABCDAB  ABCD  
              ABCDABD

子串和父串的匹配进度都前进了一大截，节省了（2*子串长+2）次匹配。

代码：

（c代码是别人撸的，我就照着写了下思考了一下，下面的python是我写的）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
void print(int a[],int len)
{
    int i=0;
    while(i<len)
    {
        printf("%d ",a[i]);
        i++;
    }
    printf("\n");
}

void prints(char a[],int s,int e)
{
    int i=s;
    while(i<e)
    {
        printf("%c",a[i]);
        i++;
    }
    printf("\n");
}
void cal_next(char * str,int * next,int len)
{
    int i,j;
    next[0]=-1;
    for(i=1; i<len; i++)
    {
        j=next[i-1];
        while(str[j+1]!=str[i]&&(j>=0))
        {
            j=next[j];
        }
        if(str[i] == str[j+1])
        {
            next[i]=j+1;
        }
        else
        {
            next[i]=-1;
        }
    }
    print(next,len);
}

int KMP(char * str,int slen,char* ptr,int plen,int *next)
{
    int s_i=0,p_i=0;
    while(s_i<slen &&p_i<plen)
    {
        if(str[s_i]==ptr[p_i])
        {
            s_i++;
            p_i++;
        }
        else
        {
            if(p_i==0)
                s_i++;
            else
                p_i=next[p_i-1]+1;
        }
    }
    return (p_i==plen)?(s_i-plen):-1;


}

int main()
{
    char str[N]= {0};
    char ptr[N]= {0};
    int slen,plen;
    int next[N];

    while(scanf("%s%s",str,ptr))
    {
        slen=strlen(str);
        plen=strlen(ptr);
        cal_next(ptr,next,plen); //计算next数组
        printf("%d\n",KMP(str,slen,ptr,plen,next));

    }
    return 0;
}

python：

# KMP算法
string,strp=input().split(",")
next=[0 for n in range(0,len(strp))] 
for i in range(0,len(strp)):
    if i==0:
        next[0]=-1
        continue
    j=next[i-1]
    while(strp[j+1]!=strp[i] and (j>=0)):
        j=next[j]
    if(strp[i]==strp[j+1]):
        next[i]=j+1
    else:
        next[i]=-1
print(next)
s_i=0
p_i=0
while(s_i<len(string) and p_i<len(strp)):
    if(string[s_i]==strp[p_i]):
        s_i+=1
        p_i+=1
    else:
        if(p_i==0):
            s_i+=1
        else:
            p_i=next[p_i-1]+1

if i==len(strp):
    print(i)
else:
    print(-1)