KMP

#include <fstream>
#include <string>
#include <vector>

std::vector<int> prefix_function(std::string s) {
    using namespace std;
    int n = s.length();
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
        int j = p[i - 1];
        while (j > 0 && s[i] != s[j])
            j = p[j - 1];
        if (s[i] == s[j])
            ++j;
        p[i] = j;
    }
    return p;
}

int main() {
    using namespace std;
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    string mainStr, subStr;
    getline(fin, mainStr);
    getline(fin, subStr);

    string kmp_str = subStr + "#" + mainStr;
    vector<int> prefix = prefix_function(kmp_str);
    bool outed = false;
    for (int i = 0; i < prefix.size(); i++) {
        if (prefix[i] == subStr.size() and !outed) {
            outed = true;
            fout << i - 2 * subStr.size() + 1;
            return 0;
        }
    }
    fout << -1;
}