3

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

const int MOD = 70000;

int BM(string s, string t) {
    vector<int> v;
    for (int i = 0; i <= s.size() - t.size(); ++ i)
        if (s[i] == t[0])
            v.push_back(i);
    for (int i = 0; i < v.size(); ++ i) {
        int j = t.size() - 1;
        for (; j >= 0; -- j) {
            if (s[v[i] + j] != t[j]) break;
        }
        if (j == -1) return v[i];
    }
    return -1;
}

int KMP(string p, string t) {
    int n = t.size();
    int m = p.size();
    int *dp = new int[m];
    for (int i = 0; i < m; ++ i)
        dp[i] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && p[j] != p[i])
            j = dp[j - 1];
        if (p[j] == p[i])
            j++;
        dp[i] = j;
    }

    int res = -1;
    j = 0;
    for (int i = 0; i < n; ++ i) {
        while (j > 0 && p[j] != t[i])
            j = dp[j - 1];
        if (p[j] == t[i])
            j++;
        if (j == m) {
            res = i - j + 1;
            break;
        }
    }
    delete [] dp;
    return res;
}

int main(void) {
    string s, t;
    cin >> s >> t;
    int rb = BM(s, t);
    int kmp = KMP(t, s);
    cout << "Boyer-Mour: " << rb << endl;
    cout << "KMP: " << kmp << endl;
    return 0;

}