剪花布条 HDU-2087

本文主要是介绍剪花布条 HDU-2087，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://vjudge.net/problem/HDU-2087

居然WA

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int nxt[1010];
void get_nxt(char t[]){
    int j=0, k=-1;
    nxt[0]=-1;
    int tlen=strlen(t);
    while(j<=tlen){
        if(k==-1 || t[k]==t[j])
            nxt[++j]=++k;
        else
            k=nxt[k];
    }
    for(int i=0; i<tlen; i++)
        printf("%d ", nxt[i]);
}
void kmp(char s[], char t[]){
    get_nxt(t);
    int i=0, j=0;
    int ans=0;
    int slen=strlen(s), tlen=strlen(t);
    while(i<slen){
        if(j==-1 || s[i]==t[j]){
            i++, j++;
            if(j>=tlen)//匹配完后重新开始，所以j=0 ， 注意与 P3375区别 
                ans++,j=0;
        }
        else
            j=nxt[j];
    }
    printf("%d\n", ans);
}
int main()
{
    char str[2020], s[1010], t[1010];
    while(gets(str) && str[0]!='#'){
        sscanf(str, "%s %s", s, t);
        kmp(s, t);
    }

    return 0;
}
/*
abaabaabeca abaabe
aabaaabaaaabea aaaab
aaaaaa aa
*/

这篇关于剪花布条 HDU-2087的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！