HDU-2087 C - 剪花布条(KMP基本)

发布时间：2020-12-16 09:16:06 所属栏目：百科来源：网络整理

导读：http://acm.hdu.edu.cn/showproblem.php?pid=2087 ? 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？? Input输入中含有一些数据，分别是成对出现的花布

http://acm.hdu.edu.cn/showproblem.php?pid=2087

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

Input输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。?
Output输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。?
Sample Input

abcde a3
aaaaaa  aa
#

Sample Output

0
3

　　对于aaaaaa  aa这个样例，为：aa　　aa 　　aa  为三个。不可重叠。
　　kmp基本的求next数组。代码中,当j==-1时 ，表示匹配完成一段，判断时当j==-1时，i++，跳入下一个匹配段,j=0表示从匹配段的头开始。
　　比如对于aaaaaa这个样例：
　　　　　　aa
　　　　　　此时i==1,j==1，匹配成功，执行i++,j++　————>i=2，j=2.由于长度正好为2，则————>i--，j=-1,得i=1,j=-1;
　　　　　　j=-1，则————>j++，i++————>j=0,i=2。保证了不重叠，使代码简洁无需额外判断，长度正好时，i被多加，则再减回来，再加回去。
　　　　　　好像有点绕...看代码吧
　　代码：

#include<iostream>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn=1e5+10;
char a[maxn],b[maxn];
int nex[maxn];
void getnext(int len)
{
    nex[0]=-1;
    int k=-1;
    int j=0;
    while(j<len)
    {
        if(k==-1||a[j]==a[k])
        {
            ++k;
            ++j;
            nex[j]=k;
        }
        else
            k=nex[k];
    }
    return ;
}    
int main()
{
    while(scanf("%s",a))
    {
        if(a[0]==‘#‘)
            break;
        scanf("%s",b);
        int ans=0;
        int lenb=strlen(b);
        getnext(lenb);
        int lena=strlen(a);
        int i=0,j=0;
        while(i<lena&&j<lenb)
        {
            if(j==-1||a[i]==b[j])
            {    
        //        printf("匹配成功：i=%d  j=%dn",i,j);
                　　i++;j++;
                
            }
            else
            {
                j=nex[j];
            }
            if(j==lenb)
            {
                ans++;
                j=-1;                                
                i--;
            //    printf("i: %dn",i);
            }
        }
        cout<<ans<<endl;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!