HDU 2087 剪花布条——————KMP,求子串在母串中的出现次数，不重叠

小鱼儿 2022-05-16 09:00 85阅读 0赞

# 剪花布条 #

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 29362 Accepted Submission(s): 17994**

Problem Description

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

Input

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见\#字符，则不再进行工作。

Output

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

Sample Input

abcde a3 
       
        
    
    aaaaaa  aa

Sample Output

0 
       
        
    
    3

--------------------

求子串在母串中的出现次数，这题和 [HDU 1686][] 不同，此题查找的是不重叠的出现次数，而 [HDU 1686][]找的则是可以重叠的

比如：

母串  
*a**a**a**a**a**a**a**a*  a a a a a a a a 八个a

子串  
*a**a*  a a

结果应该是  
ans=4

--------------------

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1007;
    char s[MAXN],p[MAXN];
    int slen,plen,nex[MAXN];
    
    void GetNext()
    {
        int i,j;
        i=0;
        j=nex[0]=-1;
        while(i<plen)
        {
            while(-1!=j && p[i]!=p[j])  j=nex[j];
            if(p[++i]==p[++j])          nex[i]=nex[j];
            else                        nex[i]=j;
        }
    }
    int KMP()
    {
        GetNext();
        int i,j,ans;
        i=j=ans=0;
        while(i<slen)
        {
            while(-1!=j && s[i]!=p[j]) j=nex[j];
            ++i;++j;
            if(j>=plen)
            {
                ans++;
                j=0;//这里
            }
        }
        return ans;
    }
    
    int main()
    {
        while(~scanf("%s",s)&&s[0]!='#')
        {
            scanf("%s",p);
            slen=strlen(s);
            plen=strlen(p);
            printf("%d\n",KMP());
        }
        return 0;
    }

hash因该也能过，下次试一下hash

[HDU 1686]: http://acm.hdu.edu.cn/showproblem.php?pid=1686