首页 > 其他 > 详细

HDU - 2087 求不可重复字符串的匹配次数

时间:2018-02-09 21:35:49      阅读:216      评论:0      收藏:0      [点我收藏+]

只要KMP里对f[i]进行限制即可

/*H E A D*/
int nxt[maxn],f[maxn],ans;
char T[maxn],P[maxn];
void buildNext(){
    int m=strlen(P+1);
    int j=0;
    nxt[1]=0;
    rep(i,2,m){
        while(j>0&&P[i]!=P[j+1]) j=nxt[j];
        if(P[i]==P[j+1])j++;
        nxt[i]=j;
    }
}
void match(){
    int n=strlen(T+1);
    int m=strlen(P+1);
    int j=0;
    rep(i,1,n){
        while(j>0&&(j==m||T[i]!=P[j+1])) j=nxt[j];
        if(T[i]==P[j+1]) j++;
        f[i]=j;
        if(f[i-1]==m) f[i]=min(1,j);
        if(f[i]==m)ans++;
    }
}
int main(){
    while(~s1(T)){
        if(T[1]==‘#‘)break;
        s1(P);
        ans=0;
        buildNext();
        match();
        println(ans);
    }
    return 0;
}

HDU - 2087 求不可重复字符串的匹配次数

原文:https://www.cnblogs.com/caturra/p/8436579.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!