3

#include <iostream>
#include <string>

using namespace std;
typedef unsigned long long uii;

const int MOD = 65537;

int Brute(string p, string t) {
    int n = t.size();
    int m = p.size();
    int b = 0;
    int x = -1;
    for (int i = 0; i <= n - m; ++ i) {
        for (b = 0; b < m && p[b] == t[i + b]; ++ b);
        if (b == m) {
            x = i;
            break;
        }
    }
    return x;
}

int pm(int a, int b, int c) {
    if (b == 0) return 1;
    if (b % 2 == 1) return (int)(((uii)a * (uii)pm(a, b - 1, c)) % (uii)c);
    else {
        uii x = (uii)pm(a, b / 2, c);
        return (int)((x * x) % (uii)c);
    }
}

int f(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) * ((pm(x, n - i - 1, q) % q)) % q)) % q;
    }
    return res;

}

int g(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) * pm(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 RK(string p, string t) {
    int n = t.size();
    int m = p.size();
    int hashp = f(p, 0, m, MOD);
    int hasht = f(t, 0, m, MOD);
    for (int i = 0; i <= n - m; ++ i) {
        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 = g(t, hasht, i, i + m, MOD);
    }
    return -1;
}

int main(void) {
    string t, p;
    cout << "Input string>";
    cin >> t;
    cout << "Input sample>";
    cin >> p;
    int res1 = Brute(p, t);
    int res2 = RK(p, t);
    cout << res1 << endl << res2 << endl;
    return 0;
}