求子字符串在父字符串出现的次数

Question

速度一定要比普通遍历方法快，求大佬🧍‍♂️

Answer 1

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 2e5 + 100;
int Next[MAXN];
int ans = 0;
void Priefix_Table(string pattern){
    Next[0] = Next[1] = 0;
    int j;
    int len = pattern.length();
    for(int i=1;i<len;i++){
        j = Next[i];
        while(j && pattern[i] != pattern[j]) j = Next[j];
        if(pattern[i] == pattern[j]) Next[i+1] = j + 1;
        else Next[i+1] = 0;
    }
}
void KMP(string text, string pattern){
    int len_text = text.length();
    int len_pattern = pattern.length();
    int j=0;
    for(int i=0;i<len_text;i++){
        while(j && text[i] != pattern[j]) j = Next[j];
        if(text[i] == pattern[j]) j++;
        if(j == len_pattern) ans++;
    }
}
int main(){
    string s1, s2;
    cin >> s1 >> s2;//s1为父串,s2为子串
    Priefix_Table(s2);
    KMP(s1, s2);
    cout << ans;
    return 0;
}