|POJ 3461|KMP|Oulipo

2019-11-06 07:02:01

字体：大中小

来源：转载

供稿：网友

Poj传送门纯KMP模板题，又复习了一下模板

#include<cstdio> #include<algorithm> #include<cstring> #include<vector>#define ms(i,j) memset(i,j, sizeof i);using namespace std;const int MAXL = 1000000 + 5; int T; char s1[MAXL], s2[MAXL];int f[MAXL];void getfail(){ f[0] = f[1] = 0; int len = strlen(s2); for (int i=1;i<len;i++) { int j = f[i]; while (j && s2[i]!=s2[j]) j = f[j]; f[i+1] = ((s2[i]==s2[j]) ? (j+1) : (0)); }}int kmp(){ int ret = 0; int len = strlen(s1); int m = strlen(s2); int j = 0; for (int i=0;i<len;i++) { while (j && s1[i]!=s2[j]) j = f[j]; if (s1[i]==s2[j]) j++; if (j==m) ret++; } return ret;}int main() { scanf("%d", &T); while (T--) { scanf("%s%s", s2, s1); getfail(); PRintf("%d/n", kmp()); } return 0; }

上一篇：leetcode 23. Merge k Sorted Lists

下一篇：单链表的简单实现