3

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

using namespace std;

const int MOD = 70000;

int powmod(int n, int p, int q) {
    if (p == 0)
        return 1;
    return (powmod(n, p - 1, q) * n) % q;
}

int hashgen(string s, int a, int b, int q) {
    int x = 2;
    int res = 0;
    int n = b - a;
    for (int i = 0; i < n; ++ i) {
        res = ((res % q) + ((s[a + i] % q) * ((powmod(x, n - i - 1, q) % q)) % q)) % q;
    }
    return res;

}

int rehash(string s, int oldhash, int oldc, int newc, int q) {
    int x = 2;
    int step = newc - oldc - 1;
    int newhash = oldhash;
    int d1 = ((s[oldc] % q) * powmod(x, step, q)) % q;
    while (newhash < d1) newhash += q;
    newhash = (newhash - d1) % q;
    newhash = (newhash * (x % q)) % q;
    newhash = (newhash + (s[newc] % q)) % q;
    return newhash;
}

int RB(string p, string t) {
    int n = t.size();
    int m = p.size();
    int hashp = hashgen(p, 0, m, MOD);
    int hasht = hashgen(t, 0, m, MOD);
    for (int i = 0; i <= n - m; ++ i) {
        //printf("i = %d\nhashp = %d\nhasht = %d\n\n", i, hashp, hasht);
        if (hasht == hashp) {
            int j = 0;
            for (; j < m && p[j] == t[i + j]; ++ j);
            if (j == m)
                return i;
        }
        if (i < n - m)
            hasht = rehash(t, hasht, i, i + m, MOD);
    }
    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 = RB(t, s);
    int kmp = KMP(t, s);
    cout << "Rabin-Karp: " << rb << endl;
    cout << "KMP: " << kmp << endl;
    return 0;

}