POJ 3461 Oulipo（KMP求匹配次数）

/*题意：求某一单词在句子中出现的次数。做这道题的时候，匹配算法搞了很久，最后终于想明白了，受传统模式匹配算法的影响，认为①处也需要对i做一次变化。*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int wMax = 10010;const int tMax = 1000010;char s[wMax], ss[tMax];int next[wMax];int ans;void getNext(char *s, int *next, int len){int i, j;i = 0, j = -1;next[0] = -1;while(i <= len){if(j == -1 || s[i] == s[j]){i ++;j ++;if(s[i] == s[j])//求next[]时候需要做的优化,aaaaab情况next[i] = next[j];elsenext[i] = j;}elsej = next[j];}}void match(char *s, int len1, char *ss, int len2){int i, j;for(i = 0, j = 0; i < len2;){if(j == - 1 || ss[i] == s[j]){i ++;j ++;if(j == len1)//匹配成功情况下的特殊处理{ans ++;j = next[j];}}else//①这里i不需要变化，只需要在上面那种情况下才改变{j = next[j];}}}int main(){//freopen("e://data.in", "r", stdin);int T;scanf("%d", &T);while(T --){ans = 0;scanf("%s%s", s, ss);int len1 = strlen(s);getNext(s, next, len1);int len2 = strlen(ss);match(s, len1, ss, len2);printf("%d\n", ans);}return 0;}