KMP 字符串匹配

算法思路

现在有s1,s2两个字符串,其中s2是短串,s1是长串。试问s2是否是s1的字串?

朴素算法:

设s1长度为n,s2长度为m。
s2字符串首位从s1字符串首位到n-m为一一比较,比较时一个字符一个字符比较。
时间复杂度:O(nm)

s1.find(s2)就是用的朴素算法。

KMP

我们将最长前后缀定义为:一个串的前缀和后缀一摸一样的最长长度。例如:
abceduabc的最长前后缀就是abc。

用next[i]表示从s[0]~s2[i-1]子串的最长的前后缀的长度,例如:
对于s2=abcukabcug:
next[1]=0,next[2]=0,next[3]=0,next[4]=0,next[5]=0,next[6]=1,next[7]=2,next[8]=3,next[9]=4,next[10]=0

如何算出next数组

pos是最长前后缀,i是当前子串长度。

如果s2[i]!=s2[pos]则找到次长前后缀(可能是0)
如果s2[i]==s2[pos]则next[i+1]=++pos
如果pos==0则next[i+1]=0

注意:next数组只保存的字串都是以s2[0]为首的子串。

得到next数组如何匹配

失配:即某两个字符不一样

先一个一个朴素匹配,当在next[pos]失配的时候就找到s[next[pos]]与其匹配。如果还是与s[next[pos]]也失配了,就在尝试s[next[next[pos]]],以此类推。

如果所有都匹配好就找到了。

代码

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int next[1000005];
void getnext(){
    int pos=0;
    int s2len=s2.length();
    for(int i=1;i<=s2len;i++){
        while(s2[pos]!=s2[i]&&pos>0){
            pos=next[pos];
        }
        if(s2[pos]==s2[i])next[i+1]=++pos;
        if(pos==0)next[i+1]=0;
    }
}
void KMP(){
    int pos=0;
    int s1len=s1.length();
    int cnt=0;
    for(int i=0;i<s1len;i++){
        while(s1[i]!=s2[pos]&&pos>0){
            pos=next[pos];
        }
        if(s1[i]==s2[pos])pos++;
        if(pos==s2.length())cout<<i+1-(s2.length()-1)<<endl;
    }
} 
int main(){
    cin>>s1;
    cin>>s2;
    getnext();
    KMP();
    for(int i=1;i<=s2.length();i++){
        cout<<next[i]<<" ";
    }
    return 0;
}

本文链接:https://kaispace.com.cn/index.php/archives/482/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者