首页 > 代码库 > KMP求模式串在原串中出现的次数
KMP求模式串在原串中出现的次数
#include <stdio.h> #include <string.h> #define maxn 10010 int next[maxn]; char str[maxn], buf[maxn * 100]; void getNext() { int i = 0, j = -1; next[i] = j; while(str[i]) { if(j == -1 || str[i] == str[j]) { ++i; ++j; if(str[i] == str[j]) next[i] = next[j]; else next[i] = j; } else j = next[j]; } } void KMP() { getNext(); int i = 0, j = 0, ans = 0; while(buf[i]) { if(j == -1 || buf[i] == str[j]) { ++i; ++j; if(!str[j]) { ++ans; j = next[j]; } } else j = next[j]; } printf("%d\n", ans); } int main() { // freopen("stdin.txt", "r", stdin); int N; scanf("%d", &N); while(N--) { scanf("%s%s", str, buf); KMP(); } return 0; }
KMP求模式串在原串中出现的次数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。