首页 > 其他 > 详细

POJ 3461 Oulipo

时间:2018-05-24 22:53:08      阅读:224      评论:0      收藏:0      [点我收藏+]

KMP模板题

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[1000086],b[1000086];
int Next[1000086];
int main()
{
    int T;
    int la,lb;

    scanf("%d",&T);

    while(T--){
        scanf("%s %s",a,b);
        la=strlen(a);
        lb=strlen(b);
        int j,k;
        j=0;k=-1;Next[0]=-1;
        while(j<la){
            if(k==-1||a[j]==a[k]){
                j++;
                k++;
                Next[j]=k;
            }
            else{
                k=Next[k];
            }
        }
        int ans=0;
        j=0;k=0;
        while(k<lb){
            if(j==-1||a[j]==b[k]){
                j++;k++;
            }
            else{
                j=Next[j];
            }
            if(j==la){
                j=Next[j];ans++;
            }
        }
        cout<<ans<<endl;
    }
}

 

POJ 3461 Oulipo

原文:https://www.cnblogs.com/ZGQblogs/p/9085445.html

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