#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

void getNext(const string& pattern, vector<int>& next) {
    int len = pattern.length();
    int k = -1, j = 0;
    next[0] = -1;

    while (j < len - 1) {
        if (k == -1 || pattern[k] == pattern[j]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

int KMP(const string& s, const string& p) {
    int m = s.length();
   ...