题目是这样的:给你T组数据,每组2个字符串A,B求A在B中出现次数(超过106个字符)

所以只能用KMP

简单介绍一下KMP(刚学)

在字符串匹配的过程中,若使用O(NM)暴力算法,显然会有很多多余匹配的操作。比如 匹配 aaaaaaaaaaaaab 和 aaaab。前面那么多 a 你就一个个挨着匹配不累啊。所以有了KMP算法。
KMP算法的主体思想是:利用NEXT数组在A,B的某一位匹配失败时主动将B串前移一定位数,跳过绝对不会出现匹配情况的串部分。而NEXT数组是什么呢?

NEXT[i]表示 待匹配串B的长度为i的前缀 的 长度相同且字符相同(说白了就是完全相同)的前缀和后缀的最长长度。

如对于 ababcaba : NEXT[3]=1 ,NEXT[4]=2 ,NEXT[5]=0 ,NEXT[8]=3…
这样,当如图的情况时,我们可以让B串前移NEXT[i-1]位

这样,我们就可以很快求出B是否为A的字串。

于是,现在最大的问题就是如何求NEXT数组

方法:若现在我们已经求出了NEXT[i],就会有如下的两种情况(注意NEXT下标为长度而B为字符串的位)
a. B[i]==B[NEXT[i]+1],此时NEXT[i+1]=NEXT[i]+1;
b. B[i]!=B[NEXT[i]+1],此时NEXT[i+1]可以由一种高深的方法得到:不断寻找B前i位的公共前后缀的公共前后缀…直到某一个前缀的后一位与B[i]相同,NEXT[i+1]={此时的NEXT};
#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 1000001
#define ML 10001

using namespace std;

int tot,nxt[ML];
char tar[MX],str[ML];

void getnext(int slen)
{
    int i=0,j=-1;
    nxt[0]=-1;
    while(i<slen)
    {
        if(j==-1||str[i]==str[j])nxt[++i]=++j;
        else j= nxt[j];
    }
}

int KMP(int slen,int tlen)
{
    int i=0,j=0,ans=0;
    while(i<tlen)
    {
        if(tar[i]==str[j]||j==-1)i++,j++;
        else j=nxt[j];
        if(j==slen)ans++,j=nxt[j-1],i--;
    }
    return ans;
}

int main()
{
    int t,slen,tlen;
    scanf("%d",&t);
    for(int w=1; w<=t; w++)
    {
        scanf("%s%s",str,tar);
        slen=strlen(str),tlen=strlen(tar);
        tot=0;
        getnext(slen);
        printf("%d\n",KMP(slen,tlen));
    }
    return 0;
}
分类: 所有

1 条评论

蒟蒻XZY · 2017年4月18日 11:56 下午

%%%%%太强啦

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *