Problem Description

一塊花布條，里面有些圖案，另有一塊直接可用的小飾條，里面也有一些圖案。對于給定的花布條和小飾條，計算一下能從花布條中盡可能剪出幾塊小飾條來呢？?

Input

輸入中含有一些數據，分別是成對出現的花布條和小飾條，其布條都是用可見ASCII字符表示的，可見的ASCII字符有多少個，布條的花紋也有多少種花樣。花紋條和小飾條不會超過1000個字符長。如果遇見#字符，則不再進行工作。?

Output

輸出能從花紋布中剪出的最多小飾條個數，如果一塊都沒有，那就老老實實輸出0，每個結果之間應換行。

Sample Input

abcde a3
aaaaaa ?aa
#

Sample Output

0
3

思路：KMP 模版題，求文本串中模式串出現的次數，需要注意的是，重復字符無法使用，每次匹配成功需要初始化模式串位置

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=20091226; const int N=1000001; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;int Next[N]; char str1[N],str2[N]; void getNext(char p[]){Next[0]=-1;int len=strlen(p);int j=0;int k=-1;while(j<len){if(k==-1||p[j]==p[k]) {k++;j++;Next[j]=k;}else{k=Next[k];}} } int KMP(char t[],char p[]) {int tLen=strlen(t);int pLen=strlen(p);getNext(p);int res=0;int j=0;for (int i=0;i<tLen;i++){while(j&&p[j]!=t[i]){j=Next[j];}if(p[j]==t[i]){j++;}if(j==pLen){res++;j=0;//字符不能重復使用，初始化模式串位置}}return res; }int main(){while(scanf("%s",str1)){if(str1[0]=='#')break;getchar();scanf("%s",str2);memset(Next,0,sizeof(Next));printf("%d\n",KMP(str1,str2));}return 0; }

?

總結

以上是生活随笔為你收集整理的剪花布条（HDU-2087）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。