首页 > 代码库 > hdu 1686 Oulipo
hdu 1686 Oulipo
题目:
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1686
题意:
输入t,是测试组数。每组测试,依次输入 字符串s1和s2。求出s2中s1的个数,可以有重叠。
思路:
KMP算法。
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s1[10010],s2[1000010]; int next[10010]; int len1,len2; void get_nextval(char s[],int len) { int i,j; i = -1; j = 0; next[0] = -1; while(j<len) { if(i == -1 || s[i] == s[j]) { j++; i++; next[j] = i; } else i = next[i]; } } int KMP(int m,int n)//m是s1串的长度,n是s2串的长度 { int i=0,j=0; int num=0;//s2中s1的个数,和hdu 2087不同的是,s2中的s1可以有重叠(关键看s1的next数组) while(i<n) { if(s1[j] == s2[i] || j==-1) { i++;j++; if(j==m) { num++; j=next[j]; } } else j=next[j]; } return num; } int main() { //freopen("input.txt","r",stdin); int t; cin>>t; getchar(); while(t--) { gets(s1); gets(s2); len1 = strlen(s1); len2 = strlen(s2); get_nextval(s1,len1); cout<<KMP(len1,len2)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。