首页 > 代码库 > hdu1686 KMP裸题
hdu1686 KMP裸题
秋招快有着落啦,十一月中去北京区赛膜拜众神。
哎,好长一段时间没有刷过,重头拾起,最近得专题是字符串。
Trie前一排又敲了一遍,KMP今天敲了一下。
题目一大堆废话,实际就是判断模式串出现得次数,我是对着算法导论伪代码敲得,一次AC,真得很水。
/*********************************************************** > OS : Linux 3.13.0-24-generic (Mint-17) > Author : yaolong > Mail : dengyaolong@yeah.net > Time : 2014年09月24日 星期三 15时31分51秒 **********************************************************/ #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; int next[12345]; char p[12345]; char T[1234567]; void build_next ( int m ) { next[1] = 0; int k = 0; for ( int q = 2; q <= m; q++ ) { while ( k > 0 && p[k + 1] != p[q] ) { k = next[k]; } if ( p[k + 1] == p[q] ) { k = k + 1; } next[q] = k; } } int kmp ( int n, int m ) { build_next ( m ); int q = 0; int res = 0; for ( int i = 1; i <= n; i++ ) { while ( q > 0 && p[q + 1] != T[i] ) { q = next[q]; } if ( p[q + 1] == T[i] ) { q = q + 1; } if ( q == m ) { //cout << "Here" << i-m<<"q"; ++res; q = next[q]; //cout<<q<<endl; } } return res; } int main() { int C; p[0]=T[0]='1'; while(scanf("%d",&C)!=EOF){ while(C--){ scanf("%s",p+1); scanf("%s",T+1); printf("%d\n",kmp(strlen(T)-1,strlen(p)-1)); } } }
hdu1686 KMP裸题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。