剪花布条【HDOJ2087】

本文主要是介绍剪花布条【HDOJ2087】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
解题思路：这是KMP算法模板的应用。需要注意的地方就是，这里的子串需要重新取，所以对于j的处理时要改变一下。

版本1

#include <cstdio>
#include <cstring>
#include <cstdlib>
const int maxn = 1010;
int next[maxn];
char str[maxn],pat[maxn];
void getNext(char s[],int len){int j=-1;next[0]=-1;for(int i =1;i<len;i++){while(j!=-1&&s[i]!=s[j+1]){j=next[j];}if(s[i]==s[j+1]){j++;}next[i]=j;}
} 
//统计pattern串在text串中出现的次数
int KMP(char text[],char pattern[]){int n=strlen(text);int m=strlen(pattern);getNext(pattern,m);int ans = 0,j=-1;for(int i=0;i<n;i++){while(j!=-1&&text[i]!=pattern[j+1]){j=next[j];}if(text[i]==pattern[j+1]){j++;}if(j==m-1){ans++;j=next[0];}}return ans;
} 
int main(){while(scanf("%s",str)!=EOF&&str[0]!='#'){scanf("%s",pat);memset(next,0,sizeof(next));int tmp=KMP(str,pat);printf("%d\n",tmp);}return 0;
}

版本2

根据左神进阶视频讲解改写而成，十分感谢左神，终于让我弄懂了KMP算法。

#include<cstdio>
#include<cstring>
using namespace std;
char str1[1005],str2[1005];
int next[1005];
void getNext(char str[],int len){int i=2,cn=0;next[0]=-1;next[1]=0;while(i<len){if(str[i-1]==next[cn]) next[i++] = ++cn;else if(cn > 0) cn = next[cn];else next[i++] = 0;}
}
int main(){while(scanf("%s",str1)&&str1[0]!='#'){scanf("%s",str2);int len1 = strlen(str1);int len2 = strlen(str2);int j=0,i=0,cnt=0;getNext(str2,len2);while(i<len1){if(str1[i] == str2[j]){i++; j++;}else{ //甲乙没配上，则乙往右推 if(next[j]==-1){ //推不动了，乙已经在0位置了，则只能让甲移动 i++; }else{ //乙还能推,则推到j的最长前缀的下一个位置 j = next[j];  } }if(j == len2){ //说明已经匹配上str2了，但是还要继续找 j=0;cnt++;} }printf("%d\n",cnt);}return 0;
}

这篇关于剪花布条【HDOJ2087】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---