【HDU-2087】解题报告（KMP，去重）

原始题目

剪花布条

  • Time Limit: 1000/1000 MS (Java/Others)
  • Memory Limit: 32768/32768 K (Java/Others)
  • Total Submission(s): 28902
  • Accepted Submission(s): 17700

Problem Description

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

Input

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

Output

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

Sample Input

abcde a3
aaaaaa  aa
#

Sample Output

0
3

Author

qianneng

Source

冬练三九之二

Recommend

lcy

题目大意

如题 # 解题思路 - 模板加一句\(Next[len]=0\)，去重即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//#include <bits/stdc++.h>
#include <cstdio> 
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PI acos((double)-1)
#define E exp(double(1))
#define K 1000000+9
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define ms(x,a) memset((x),(a),sizeof(a))
int nt[10006];
char a[K],b[10005];
int n,m;
//参数为模板串和next数组
//字符串均从下标0开始
void kmpGetNext(char *s,int *Next)
{
    Next[0]=0;
    int len=strlen(s);
    for(int i=1,j=0;i<len;i++)
    {
        while(j&&s[i]!=s[j]) j=Next[j];
        if(s[i]==s[j]) j++;
        Next[i+1]=j;
    }
//    Next[len]=0;
}
int kmp(char *ss,char *s,int *Next)
{
    kmpGetNext(s,Next);
//  调试输出Next数组
//	int len=strlen(s);
//	for(int i=0;i<=len;i++)
//		cout<<Next[i]<<" ";
//	cout<<endl; 

    int ans=0;
    int len1=strlen(ss);
    int len2=strlen(s);
    for(int i=0,j=0;i<len1;i++)
    {
        while(j&&ss[i]!=s[j])j=Next[j];
        if(ss[i]==s[j]) j++;
        if(j==len2){
        	ans++;
//			return i-len2+2;
		}
           
    }
//    return -1;
	return ans;
}

int main(void)
{
//	ios::sync_with_stdio(false);
    int t;
    scanf("%d",&t); 
    while(t--)
    {
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	scanf("%s",a);
    	scanf("%s",b);
    	cout<< kmp(a,b,nt)<<endl;
    }

    return 0;
}

收获与反思

  • KMP水题