boyer moore substring

#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

vi preBmBc(string x){
    vi t(256 , sz(x));
    rep(i , sz(x) - 1){
        t[x[i]] = sz(x) - i - 1;
    }
    return t;
}

bool isPrefix(string x , int p){
    int i;
    int suffixlen = sz(x) - p;

    for (i=0; i < suffixlen; i++) {
        if (x[i] != x[p+i]) {
            return 0;
        }
    }
    return 1;
}

int suffixLength(string x , int p) {
    int i;
    for (i = 0; (x[p-i] == x[sz(x)-1-i]) && (i < p); i++);
    return i;
}

vi preBmGs(string x){
    vi t(sz(x));
    int p;
    int last_prefix_index = 1;
    for (p=sz(x)-1; p>=0; p--) {
        if (isPrefix(x , p+1)) {
            last_prefix_index = p+1;
        }
        t[p] = (sz(x)-1 - p) + last_prefix_index;
    }
    for (p=0; p < sz(x)-1; p++) {
        int slen = suffixLength(x , p);
        if (x[p - slen] != x[sz(x)-1 - slen]) {
            t[sz(x)-1 - slen] = sz(x)-1 - p + slen;
        }
    }
    return t;
}

int BM(string s , string x){
    if(!sz(x)){
        return -1;
    }

    vi bmBc = preBmBc(x);
    vi bmGs = preBmGs(x);


    int n_shifts = 0;

    int i = sz(x)-1;
    while (i < sz(s)) {
        int j = sz(x)-1;
        while (j >= 0 && (s[i] == x[j])) {
            --i;
            --j;
        }
        if (j < 0) {
            return i + 1;
        }
        i += max(bmBc[s[i]], bmGs[j]);
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    string s , x;
    cin >> s >> x;
    die(BM(s , x));


    return 0;
}