(串的模式匹配4.6.2)POJ 3461 Oulipo(KMP算法的应用——求一个单词在一行文本中的出现次数)
/* * POJ_3461.cpp * * Created on: 2013年10月25日 * Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxw = 10000 + 10;const int maxt = 1000000 + 10;//统计w在s中出现的次数int match(char w[] , char s[] , int next[]){int wlen = strlen(w);int slen = strlen(s);int cnt = 0;int cur = 0 , p = 0;while(cur < slen){if(s[cur] == w[p]){++cur;++p;}else if(p >= 0){p = next[p];}else{++cur;p=0;}if(p == wlen){++cnt;p = next[p];}}return cnt;}int main(){int t;scanf("%d",&t);while(t--){char w[maxw],s[maxt];scanf("%s%s",&w,&s);int suffix[maxw];//应用KMP算法计算单词w的前缀函数suffix[0] = -1;suffix[1] = 0;int cur,p =0;for(cur = 2 ; cur<=strlen(w) ;++cur){while(p >= 0 && w[p] != w[cur-1]){p = suffix[p];}suffix[cur] = ++p;}printf("%d\n",match(w,s,suffix));}return 0;}