#include <bits/stdc++.h>
using namespace std;

vector<int> array_temporario(string & padrao){
    vector<int> index;
    int j = 0, i;
    for(i = 1; i < padrao.length();)
        if(padrao[i] == padrao[j]){
            index.push_back(j+1);
            j++;
            i++;
        } else {
            index.push_back(0);
            i++;
        }
    return index;
}

int KMP(string & texto, string & padrao){
    vector<int> index = array_temporario(padrao);
    int i = 0, j = 0;
    while(i < texto.length() && j < padrao.length()){
        if(texto[i] == padrao[j]){
            i++; j++;
        } else {
            if(j != 0) j = index[j-1];
            else i++;
        }
    }
    return i-padrao.length();
}

int main(){
    string texto = "abcxabcdabcdabcy", padrao = "abcdabcy";
    cout << KMP(texto, padrao) << endl;
}