HDU1686 Oulipo 发表于 2018-11-12 | 分类于 HDU | 字数统计: 197 字 题目链接 题解KMP模板题…1234567891011121314151617181920212223242526272829303132333435363738#include <bits/stdc++.h>using namespace std;void build_fail(char *pat, int len, int *fail){ fail[0] = -1; for(int i = 1, j = -1; i < len; ++i){ while(j > -1 && pat[i] != pat[j + 1]) j = fail[j]; if(pat[i] == pat[j + 1]) fail[i] = ++j; else fail[i] = -1; }}int KMP_match(char *text, int l1, char *pat, int l2, int *fail){ int cnt = 0; for(int i = 0, j = -1; i < l1; ++i){ while(j > -1 && text[i] != pat[j + 1]) j = fail[j]; if(text[i] == pat[j + 1]) j++; if(j == l2 - 1) j = fail[j], cnt++; } return cnt;}int n, m, fail[10005] = {0};char a[10005], b[1000005];int main(){ int T; scanf("%d", &T); while(T--){ scanf("%s%s", a, b); m = strlen(a), n = strlen(b); build_fail(a, m, fail); printf("%d\n", KMP_match(b, n, a, m, fail)); } return 0;}
v1.5.2