记录编号	406239	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2017-05-18 10:23:07	内存使用	1.31 MiB

# include <bits/stdc++.h>
using namespace std;

char word[10023], text[1000023];
int ne[10023];
inline void get_ne(char *st) {
	int n = strlen(st);
	int i = 0, j = -1;
	ne[0] = -1;
	while(i < n) {
		while(~j && st[i] != st[j]) j = ne[j];
		ne[++i] = ++j;
	}
}
inline int KMP(char *str, char *st) {
	int i = 0, j = 0;
	int ans = 0, n = strlen(str), m = strlen(st);
	while(i < n) {
		while(~j && str[i] != st[j]) j = ne[j];
		i++, j++;
		if(j == m) ans++;
	}
	return ans;
}
int main() {
	freopen("oulipo.in", "r", stdin);
	freopen("oulipo.out", "w", stdout);
	int t = 0;
	cin >> t;
	while(t--) {
		scanf("%s%s", word, text);
		get_ne(word);
		printf("%d\n", KMP(text, word));
	}

}