首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

POJ 3461 Oulipo(KMP求婚配次数)

2012-08-29 
POJ 3461 Oulipo(KMP求匹配次数)/*题意:求某一单词在句子中出现的次数。做这道题的时候,匹配算法搞了很久,

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;}

热点排行