First.先上一份最原始的无任何优化的代码（暴力）：

#include <iostream>

#include <cstring>

using namespace std;

char s[1000],p[1000];

inline int getans(char* s,char* p){

    int sl=strlen(s),pl=strlen(p);

    int i=0,j=0;

    while(i<sl && j<pl){

        if(s[i]==p[j])

            i++,j++;

        else{

            i=i-j+1;

            j=0;

        }

    }

    if(j==pl) return i-j;

    else return -1;

}

int main(){

    cin>>s>>p;

    int ans=getans(s,p);

    cout<<ans<<endl;

    return 0;

}

对于文本串S和模拟串P，进行匹配。

i表示S串的位置，同理，j表示P串的位置;

若当前字符匹配，则进行下一个（i++,j++）;

否则，将P归零，S回溯到上一次匹配的位置;

输出的是第一次匹配的位置。

Second.开始第一次优化（KMP）：

在上述的暴力中，我们可以发现，每次失配时，i返回到了前面很远的地方，所以我们想搞这样一个东西;

它具备一个特殊性质：

在每次失配是，直接让P跳到这个位子上，大大减少复杂度。

在此，我们需要引入一个叫做next的数组;

但是，仍然有最坏的情况，就是需要重新匹配;

那么此时的next[i]=0或-1，表示重头在来;

若next[i]=k，则表示P跳过了k个字符。

简略代码：

inline int KMPsearch(char* s,char* p){

    int sl=strlen(s),pl=strlen(p);

    int i=0,j=0;

    while(i<sl && j<pl){

        if(s[i]==p[j]||j==-1)//j==-1表示匹配成功，进行后续的字符匹配

            i++,j++;

        else

            j=nxt[j];//i不用变，j直接跳到预处理好的next[j]处

    }

    if(j==pl) return i-j;

    else return -1;

}

next数组记录的是长度最大且相等的前缀后缀;

举个例子：

P1： ABA

P2： ABAB

在P1中，他有长度为1的相同前缀后缀A

在P2中，他有长度为2的相同前缀后缀AB

（盗图勿喷）

我们来求next数组;

将第一步中的长度稍作变形即可;

（同上）

整体右移一位，将第一位赋值为-1。

也可以这样理解：（与-1无关了就）

如果相等，则该位的next值就是前一位的next值加上1；

如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。

代码求next数组;

inline void GetNext2(char *p,int nxt[]){

    int pl=strlen(p);

    nxt[0]=-1;

    int k=-1;

    int j=0;

    while(j<pl-1){

        if(k==-1 || p[j]==p[k]){

            ++j,++k;

            if(p[j]!=p[k])

                nxt[j]=k;

            else nxt[j]=nxt[k];

        }

        else k=nxt[k];

    }

}

Third.对于next数组的优化：

在上文所述中，有个小问题：

就是说，在j向后跳到了next[k]时，必然失配，

就是因为p[j]=p[next[j]];

那就要处理出所有这种情况，递归

next[j]=p[next[next[j]]]。

Finally.整体代码（可直接食用哦）：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

char s[100],p[100];

int nxt[100];

inline void GetNext2(char *p,int nxt[]){

    int pl=strlen(p);

    nxt[0]=-1;

    int k=-1;

    int j=0;

    while(j<pl-1){

        if(k==-1 || p[j]==p[k]){

            ++j,++k;

            if(p[j]!=p[k])

                nxt[j]=k;

            else nxt[j]=nxt[k];

        }

        else k=nxt[k];

    }

}

inline int KMPsearch(char* s,char* p){

    int sl=strlen(s),pl=strlen(p);

    int i=0,j=0;

    while(i<sl && j<pl){

        if(s[i]==p[j]||j==-1)

            i++,j++;

        else

            j=nxt[j];

    }

    if(j==pl) return i-j;

    else return -1;

}

int main(){

    cin>>s>>p;

    GetNext2(p,nxt);

    int ans=KMPsearch(s,p);

    cout<<ans<<'\n';

    return 0;

}

巴特西

KMP入门

First.先上一份最原始的无任何优化的代码（暴力）：

Second.开始第一次优化（KMP）：

嗯，真香

最新文章

热门文章