[KMP]zoj 3587：Marlon's String

大致题意：
    给出一个模式串P和一个文本串T求存在多少种数字组合(a,b,c,d)使得Ta..b + Tc..d = P。

 

大致思路：
    可以用KMP求出模式串的每个前缀在文本串中出现的次数，再把字符串翻转过来，求出模式串的每个后缀在文本串中出现的次数，最后统计一下即可~~

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=10005;
const int mMax=1000005;
char text[mMax],pat[nMax];
int lent,lenp,next[nMax];
long long a[nMax],b[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int KMP(int flag){
    int ans=0,i=0,j=-1;
    get_next();
    for(i=0;i<lent;i++){
        while(j!=-1&&pat[j+1]!=text[i]){
            j=next[j];
        }
        if(pat[j+1]==text[i])j=j+1;
        if(j==lenp-1)ans++;  //找到一个匹配
        if(j!=-1){
            if(flag)a[j]++;
            else b[j]++;
        }
    }
    return ans;
}

int main(){
    int t,i,tmp;
    long long ans;
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%s%s",text,pat);
        lenp=strlen(pat);
        lent=strlen(text);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        KMP(1);
        for(i=lenp;i!=-1;i--){
            if(next[i]!=-1) a[next[i]]+=a[i];
        }
        for(i=0;i<lent/2;i++){
            tmp=text[i];
            text[i]=text[lent-i-1];
            text[lent-i-1]=tmp;
        }
        for(i=0;i<lenp/2;i++){
            tmp=pat[i];
            pat[i]=pat[lenp-i-1];
            pat[lenp-i-1]=tmp;
        }
     //   cout<<pat<<" "<<text<<endl;
        KMP(0);
        for(i=lenp;i!=-1;i--){
            if(next[i]!=-1) b[next[i]]+=b[i];
        }
//        for(i=0;i<lenp;i++){
//            cout<<"a"<<a[i]<<" b"<<b[i]<<endl;
//        }
        for(i=0;i<lenp-1;i++){
            ans+=a[i]*b[lenp-i-2];
        }
        cout<<ans<<endl;
//        for(i=0;i<lenp;i++){
//            cout<<"a"<<a[i]<<endl;
//        }
    }
    return 0;
}

 

 

评论

2 楼 暴风雪 2012-04-17  

ch2010091 写道

Orz

1 楼 ch2010091 2012-04-17