KMP模板
这里介绍几个说的比较好的博客:
KMP博客:KMP算法的推算
接下的就是模板:
求模式串第一次在主串出现的位置 or 匹配是否在主串出现过 :
#include<bits/stdc++.h> const int maxn = 1e6 + 10; char mo[maxn], str[maxn];///mo为模式串、str为主串 int next[maxn]; inline void GetNext() { int i = 0, j = -1, len = strlen(mo); next[i] = j; while(i < len){ while( j != -1 && mo[i] != mo[j]) j = next[j]; next[++i] = ++j; } } int KmpIndex() { GetNext(); int i =0, j = 0, strL = strlen(str), moL = strlen(mo); while(i < strL && j < moL){ while( j != -1 && str[i] != mo[j]) j = next[j]; i++, j++; } if(j == moL) return i - moL;///返回模式串在主串中首次出现的位置 else return -1; } int main(void) { scanf("%s %s", str, mo); printf("%d ", KmpIndex()); return 0; }
求出现次数:
#include<bits/stdc++.h> const int maxn = 1e6 + 10; char mo[maxn], str[maxn];///mo为模式串、str为主串 int next[maxn]; inline void GetNext() { int i = 0, j = -1, len = strlen(mo); next[i] = j; while(i < len){ // if(j == -1 || mo[i] == mo[j]) next[++i] = ++j; // else j = next[j]; while( j != -1 && mo[i] != mo[j]) j = next[j]; next[++i] = ++j; } } int KmpCount()///计算模式串在子串出现的次数 { GetNext(); int i = 0, j = 0, strL = strlen(str), moL = strlen(mo); int ans = 0; while(i < strL){ while( j != -1 && mo[j] != str[i]) j = next[j]; i++, j++; if(j == moL) ans++; } return ans;///返回模式串在主串中出现的次数(可重叠出现) } int main(void) { scanf("%s %s", str, mo); printf("%d ", KmpCount()); return 0; }