「LOJ#10043」「一本通 2.2 例 1」剪花布条 （KMP

题目描述

原题来自：HDU 2087

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

输入格式

输入数据为多组数据，读取到 # 字符时结束。每组数据仅有一行，为由空格分开的花布条和小饰条。花布条和小饰条都是用可见 ASCII 字符表示的，不会超过 1000个字符。

注意：这个 # 应为单个字符。若某字符串开头有 #，不意味着读入结束！

输出格式

对于每组数据，输出一行一个整数，表示能从花纹布中剪出的最多小饰条个数。

样例

样例输入

abcde a3 aaaaaa aa #

样例输出

0 3

数据范围与提示

对于全部数据，字符串长度 ≤1000。

题解

就跑裸的KMP就行了。

唯一要注意的是在匹配到时把k重置，就可以跑出来不相互覆盖的了。

1 /* 2 编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间 3 #224299 #10043. 「一本通 2.2 例 1」剪花布条 Accepted 100 340 ms 252 KiB C++ / 725 B qwerta 2018-10-10 15:37:39 4 */ 5 #include<iostream> 6 #include<cstdio> 7 using namespace std; 8 int nxt[1003]; 9 int main() 10 { 11 //freopen("a.in","r",stdin); 12 string s,t; 13 while(cin>>s) 14 { 15 if(s.length()==1&&s[0]=='#')break; 16 cin>>t; 17 int k=-1,lens=s.length(),lent=t.length(); 18 nxt[0]=-1; 19 for(int i=0;i<lent;++i) 20 { 21 while(k!=-1&&t[i]!=t[k+1])k=nxt[k]; 22 if(t[i]==t[k+1])k++; 23 nxt[i+1]=k; 24 } 25 k=-1; 26 int ans=0; 27 for(int i=0;i<lens;++i) 28 { 29 while(k!=-1&&s[i]!=t[k+1])k=nxt[k]; 30 if(s[i]==t[k+1])k++; 31 if(k==lent-1){ans++;k=-1;} 32 } 33 cout<<ans<<endl; 34 } 35 return 0; 36 }

 

转载于:https://www.cnblogs.com/qwerta/p/9806757.html

相关资源：垃圾分类数据集及代码