AC自动机补档第二期……不懂KMP的同学可以好好学习一下这个神奇的单字符串匹配问题的算法吧!

字符串匹配

什么叫字符串匹配呢?假设我们有一个主字符串和一个子串:

主串:abcbcglx
子串:bcgl

那么在主字符串中,有没有包含子串呢?当然,你一眼就看出,从主串的第4位到第7位恰好为子串 bcgl;这时我们的匹配算法就返回 4 也就是子串在主串中第一次出现的起始位置;若匹配失败,既主串中没有包含子串,则会返回error之类的信息。

这就是字符串的匹配。

会TLE的暴力算法

那么通常,人们是如何解决这类字符串匹配的问题的呢?很简单,暴力都能解决问题。

我们先对主串和子串进行编号

a b c b c g l x
1 2 3 4 5 6 7 8

b c g l
1 2 3 4

然后枚举主串中的每个位置为子串的起始位置,然后判断是否匹配。

但是这种算法的复杂度是O(nm)【n,m分别为主串和子串的长度】,在大范围的题目是肯定会超时的,所以我们就要推出今天的主角——KMP算法!

什么是KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法),也通常被叫做看毛片算法,时间复杂度控制在了 O(m+n)。

那么这种神奇的算法是如何运作的呢?

我们先来举一个例子:
我们首先有一个主串和一个子串:
1.JPG

我们开始逐位比较,首先a和a匹配上了:
2.JPG

b和b匹配上了:
3.JPG

c和c匹配上了:
4.JPG

x和d不匹配:
5.JPG

这时没办法,只好重新开始寻找开头,b和a无法匹配:
6.JPG

主串指针往后移,c和a无法匹配:
7.JPG

主串指针往后移,x和a无法匹配:
8.JPG

主串指针往后移,a和a终于匹配:
9.JPG

接着b和b匹配上了;
10.JPG

c和c匹配上了:
11.JPG

d和d匹配上了:
12.JPG

a和a匹配上了:
13.JPG

b和b匹配上了:
14.JPG

但是x和y无法匹配,匹配终止:
15.JPG

这时按暴力来想,子串只好前功尽弃,从头开始匹配;

但是细心的同学发现:
16.JPG

我们观察一下匹配失败的c的字符串:abcdab;
他的前缀是ab,他的后缀也是ab!

这有什么用呢?我们是在子串的abcdabc的末尾c这里匹配失败的,但是c前面我们已经正确匹配了ab,也就是说我们可以匹配一个ab开头的字符串的前两位,而子串恰好满足!

那么这个x可能是直接匹配前面这个ab后面的字符的,所以我们就在下一次的匹配时,直接跳过之前那个ab,从ab的后一个字符位置开始继续往后匹配就好了!

这就是KMP算法的精髓所在!

如何实现KMP

我们这里分为两块来实现KMP:

构造p数组

我们先要在子串上构造p数组,也就是我们上文跳来跳去的那个东西:

p[1]=0;
for(int i=2;i<=lenb;i++)
        {
            j=p[i-1];
            while(j>0 && sb[i]!=sb[j+1]) j=p[j];

            if(sb[i]==sb[j+1])p[i]=j+1;else p[i]=0;
        }

p数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

我们举个栗子!
比如:abcjkdabc,那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc,最长前缀和最长后缀相同是cbc。
abcbc,最长前缀和最长后缀相同是不存在的。

而我们在这里求解的p【i】,是说以第一个字符开始,到第i个字符的字符串的最长前缀和最长后缀相同的长度。

所以对于目标子字符串,ababaca,长度是7,所以p[1],p[2],p[3],p[4],p[5],p[6],p[7]分别计算的是
a,ab,aba,abab,ababa,ababac,ababaca的相同的最长前缀和最长后缀的长度。由于a,ab,aba,abab,ababa,ababac,ababaca的相同的最长前缀和最长后缀是“”,“”,“a”,“ab”,“aba”,“”,“a”,所以p数组的值是[0,0,1,2,3,0,1],这里0表示不存在,1表示存在长度为1,2表示存在长度为2。这是为了和代码相对应。

在主串上进行匹配

一样的按照之前讲的原理,我们类似的进行匹配就好啦!当第子串i个字符匹配失败的时候,我们就去看p【i】+1是否匹配,若不匹配,再继续看p【p【i】】+1能否匹配,以此类推,程序如下:

        int st,ed;
        j=0;
        for(int i=1;i<=lena;i++)
        {
            while(j>0 && sa[i]!=sb[j+1])j=p[j];
            if(sa[i]==sb[j+1])j++;
            if(j==lenb)
            {
                ed=i;
                st=i-lenb+1;
                break;
            }
        }

模板题

【caioj 1177】子串是否出现
题目描述
【题意】
有两个字符串SA和SB,SA是母串,SB是子串,问子串SB是否在母串SA中出现过。
如果出现过输出第一次出现的起始位置和结束位置,否则输出"NO"
【输入文件】
第一行SA(1 <= 长度 <= 100 0000)
第二行SB(1 <= 长度 <= 1000)
【输出文件】
如果SB在SA中出现过输出第一次出现的起始位置和结束位置,否则输出"NO"
【样例1输入】
aaaaabaa
aab
【样例1输出】
4 6
【样例2输入】
aaaaabaa
aax
【样例2输出】
NO

就是一道裸题,直接献上模板:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char sa[1110000],sb[1100];
int p[1100];
int main()
{
    int lena,lenb,i,j;
    scanf("%s",sa+1);lena=strlen(sa+1);
    scanf("%s",sb+1);lenb=strlen(sb+1); 
    p[1]=0;
    for(int i=2;i<=lenb;i++)
    {
        j=p[i-1];
        while(j>0 && sb[i]!=sb[j+1]) j=p[j];

        if(sb[i]==sb[j+1])p[i]=j+1;else p[i]=0;
    }
    int st,ed;
    j=0;
    for(int i=1;i<=lena;i++)
    {
        while(j>0 && sa[i]!=sb[j+1])j=p[j];
        if(sa[i]==sb[j+1])j++;
        if(j==lenb)
        {
            ed=i;
            st=i-lenb+1;
            break;
        }
    }
    if(j==lenb) printf("%d %d\n",st,ed);
    else printf("NO\n");
    return 0; 
} 

结语

讲完这篇BLOG后,我们字符串的常见处理方法就到这里结束了!以后遇到什么新的算法再补充吧!希望你喜欢这篇BLOG!
kkk.gif

Last modification:July 12th, 2018 at 05:24 pm
If you think my article is useful to you, please feel free to appreciate