vector<size_t> kmp_next(const string& t) {
    size_t j = 0, k = string::npos;
    vector<size_t> next(t.size());
    next[0] = string::npos;
    while (j < t.size() - 1) {
        if (k == string::npos || t[j] == t[k]) {
            ++j, ++k;
            if (t[j] == t[k]) next[j] = next[k];
            else next[j] = k;
        } else k = next[k];
    }
    return next;
}
size_t kmp(const string& str, const string& pattern) {
    vector<size_t> next = kmp_next(pattern);
    size_t i = 0, j = 0;
    while (i < str.size() && j < pattern.size()) {
        if (str[i] == pattern[j] || j == string::npos) ++i, ++j;
        else j = next[j];
    }
    return j >= pattern.size() ? i - pattern.size() : string::npos;
}