Oulipo HDU - 1686

#include<iostream>
#include<cstring>
using namespace std ;
const int N=1e6+10;
int n,m;
int ne[N];
char p[N],s[N];
int main() {
    int t;
    cin>>t; 
    while(t--) {
        cin>>p+1>>s+1;
        n=strlen(p+1);
        m=strlen(s+1);
        int ans=0;
        for(int i=2,j=0; i<=n; i++) {
            while(j&&p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }

        for(int i=1,j=0; i<=m; i++) {
            while(j&&s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==n) {
                ans++;
                j=ne[j];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。