KMP算法

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
string ptr, str;
int net[maxn];
void Get_Next() {//求next数组（kmp算法的关键之处）
    int i = 0, j = -1;
    net[i] = j;
    while (i < ptr.size()) {
        if (j == -1 || ptr[i] == ptr[j])net[++i] = ++j;
        else j = net[j];
    }
}
int Kmp_Search1() {//求目标串str中模式串ptr第一次出现的位置
    Get_Next();
    int i = 0, j = 0;
    while (i < str.size() && j < ptr.size()) {
        if (j == -1 || ptr[j] == str[i])++i, ++j;
        else j = net[j];
    }
    if (j == ptr.size())return i - j + 1;
    return -1;//表示没有找到
}
int Kmp_Search2() {//求目标串str中模式串ptr出现的次数 
    int i = 0, j = 0;
    int ans = 0;
    while (i < str.size()) {
        if (j == -1 || ptr[j] == str[i])++i, ++j;
        else j = net[j];
        if (j == ptr.size()) {
            ++ans;
            j = 0;
        }
    }
    return ans;
}
int main() {
    cin >> ptr >> str;
    cout << Kmp_Search1() << endl;
    cout << Kmp_Search2();
}