Hd2087 剪花布条

点击打开链接

今天做了几道kmp的题目算是对昨天学的进行总结吧。这道题的意思就是在模串中找子串的个数。

#include<stdio.h> #include<string.h> int next[1005]; int sn,sm; char s1[10005],s2[1005]; void getnext() { //puts("++");int i,j=0;next[1]=0;for(i=2;i<=sm;i++){while(j>0&&s2[j+1]!=s2[i])j=next[j];if(s2[i]==s2[j+1])j++;next[i]=j;} } int kmp() {//puts("()))");int i,j=0;int cout=0;for(i=1;i<=sn;i++){while(j>0&&s1[i]!=s2[j+1])j=next[j];if(s1[i]==s2[j+1])j++;if(j==sm){ cout++;if(i<=sn)j=0;}}return cout; } int main() {while(1){ scanf("%s",s1+1);int sum=0;memset(next,0,sizeof(next));if(!strcmp(s1+1,"#"))break;scanf("%s",s2+1);sn=strlen(s1+1);sm=strlen(s2+1);getnext();sum=kmp();printf("%d\n",sum);}return 0; }

总结

以上是生活随笔为你收集整理的Hd2087 剪花布条的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。