首页 > 代码库 > HDU 1618 Oulipo KMP题解
HDU 1618 Oulipo KMP题解
给出两个字符串,寻找一个字符串在另外一个字符串出现的频率。
原来kmp还有一个陷阱,下面注释出了,下标没步进好,就有一定几率出现超时的,也有一定几率出现错误,视具体的串而定。
修改一下就好了,kmp速度是很快的。
#include <stdio.h> #include <string.h> const int MAX_TXT = 1000001; const int MAX_WORD = 10001; int gWlen, gTlen; char word[MAX_WORD]; int next[MAX_WORD]; char txt[MAX_TXT]; void getNext() { memset(next, 0, sizeof(int) * gWlen); for (int i = 1, j = 0; i < gWlen; ) { if (word[i] == word[j]) next[i++] = ++j; else if (j > 0) j = next[j-1]; else i++; } } int kmpSearch() { int i = 0, j = 0, ans = 0; for (; gWlen-j <= gTlen-i; ) { if (word[j] == txt[i]) { j++; i++; if (j == gWlen) { ans++; j = next[j-1]; } //else i++; i++放这里会超时,是一定几率会出现超时,注意了! } else if (j > 0) j = next[j-1]; else i++; } return ans; } int main() { int T; scanf("%d", &T); getchar(); while (T--) { gets(word); gWlen = strlen(word); gets(txt); gTlen = strlen(txt); getNext(); printf("%d\n", kmpSearch()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。