[KMP求形式在主串出现次数]POJ 3461 Oulipo

[KMP求模式在主串出现次数]POJ 3461 Oulipo

传送门：http://poj.org/problem?id=3461

题目大意：给定一个主串和一个模式，求模式在主串中出现的次数。

解题思路：直接修改标准KMP函数，当匹配成功是不是跳出循环，而是直接按最后一个字符失配的情况去滑动模式串，以获取下一个可能出现的匹配。

代码：

#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int MAXN = 1000010,MAXM = 10010;char T[MAXN],P[MAXM];int Next[MAXM],N,M,C;void MakeNext(int M){ int i=0,j=-1; Next[i] = -1; while(i<M){ if(j==-1||P[i]==P[j])Next[++i] = ++j; else j = Next[j]; }}int KMP(int pos,int N,int M){ int i = pos, j = 0,ans = 0; while(i<N){ if(T[i]==P[j]||j==-1)i++,j++; else j = Next[j]; if(j==M){ ans++; j = Next[j-1]; i--; } } return ans;}int main(){ scanf("%d",&C); while(C--){ scanf("%s%s",P,T); N = strlen(T),M = strlen(P); MakeNext(M); printf("%d\n",KMP(0,N,M)); } return 0;}