KMP

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

void getNext(string str, int next[]) {
    int len = str.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len - 1) {
        if (k == -1 || str[j] == str[k]) {
            j++;
            k++;
            next[j] = k;
        }
        else {
            k = next[k];
        }
    }
}

int kmp(string str, string childstr) {
    int l = str.size();
    int ans = -1;
    int i = 0;
    int j = 0;
    int childstrl = childstr.size();

    int next[childstrl] = { 0 };
    getNext(childstr, next);

    while (i < l) {
        if (j == -1 || str[i] == childstr[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }

        if (j == childstrl) {
            ans = i - childstrl;
            break;
        }
    }

    return ans;
}