KMP

2019-10-08 08:48:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

KMP

KMP

  \(KMP\) 算法是一种改进的字符串匹配算法,由 \(D.E.Knuth\)\(J.H.Morris\)\(V.R.Pratt\) 提出的,简称 \(KMP\) 算法。常用来解决可重叠的字符串匹配问题。

基本原理

  \(KMP\) 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next数组实现,数组本身包含了模式串的局部匹配信息。
  首先对模式串进行自身匹配,得到next数组。next[i]为满足s2[i-z,...,i-1]=s2[0,...,z-1] 的最大z值,即s2的子串s2[0,...,i]最长公共前后缀的长度。
  这样在进行模式串与文本串的匹配时(假设当前为文本串的s1[i]与模式串的s2[j]进行匹配),一旦发生失配情况,可以只移动模式串而不回溯指针。移动时,只需要将s2[0,...,j-1]前缀移动到后缀的位置,然后,从模式串子串s2[0,...,j-1]前缀的下一位即第next[j]位开始与文本串当前位第i位进行匹配。

效率分析

  一般情况下, \(KMP\) 算法的期望时间复杂度为 \(O(n+m)\) ,其中 \(n,m\) 分别是文本串和模式串的长度。

核心代码

ll len1,len2,next[maxn],pos[maxn],ans;
string s1,s2;
void pre()
{
    len2=s2.length();
    ll j=0;
    next[0]=0;                              /*初始化*/
    for(ll i=1;i<len2;i++)
    {
        while(j&&s2[i]!=s2[j])j=next[j];    /*如果失配,模式串指针移到s2[0,...,j]前缀后一位*/
        if(s2[i]==s2[j])j++;                /*如果相同,长度+1*/
        next[i+1]=j;
    }
}
void KMP()
{
    len1=s1.length();
    pre();
    ll j=0;
    for(ll i=0;i<len1;i++)
    {
        while(j&&s1[i]!=s2[j])j=next[j];    /*如果失配,模式串指针移到s2[0,...,j]前缀后一位*/
        if(s1[i]==s2[j])j++;                /*如果相同,长度+1*/
        if(j==len2)                         /*如果匹配到末尾*/
        {
            pos[++ans]=i-j+2;               /*记录匹配起始位置*/
            j=next[j];                      /*模式串指针移到s2[0,...,j]前缀后一位*/
        }
    }
    return;
}

例题解析

洛谷 P3375 【模板】KMP字符串匹配

  给出一个文本串 \(s_1\) 和一个模式串 \(s_2\) ,求 \(s_2\)\(s_1\) 中出现的所有位置并输出前缀数组。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define maxm 200005
#define INF 1234567890
#define p 1000000007
template<class T>inline bool reads(T &x)
{
    register char c=getchar();
    while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar();
    if(c==EOF)return false;
    while(c!=' '&&c!='\n'&&c!='\r'&&c!='\t')x+=c,c=getchar();
    return true;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
template<class T>inline void print(T x,char c){print(x),putchar(c);}
ll len1,len2,next[maxn],pos[maxn],ans;
string s1,s2;
void pre()
{
    len2=s2.length();
    ll j=0;
    next[0]=0;
    for(ll i=1;i<len2;i++)
    {
        while(j&&s2[i]!=s2[j])j=next[j];
        if(s2[i]==s2[j])j++;
        next[i+1]=j;
    }
}
void KMP()
{
    len1=s1.length();
    pre();
    ll j=0;
    for(ll i=0;i<len1;i++)
    {
        while(j&&s1[i]!=s2[j])j=next[j];
        if(s1[i]==s2[j])j++;
        if(j==len2)
        {
            pos[++ans]=i-j+2;
            j=next[j];
        }
    }
    return;
}
int main()
{
    reads(s1),reads(s2);
    KMP();
    for(ll i=1;i<=ans;i++)print(pos[i],'\n');
    for(ll i=1;i<=len2;i++)print(next[i],' ');
    return 0;
}

原文链接:https://www.cnblogs.com/LengYun/p/11629012.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:长乐国庆集训Day1

下一篇:利用Code::Blocks搭建64位C++开发平台