113B - Petr - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(A) A.rbegin(),A.rend()
#define pb push_back 
#define dbg(x) do {cerr << #x <<" = " << (x) << endl; } while (false)
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
//cout << setprecision(12) << fixed;

const ll mod = 998244353;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
long long random(long long l, long long r){
    return uniform_int_distribution<long long>(l,r)(rng);
}

const int k = 2;
const ll b[] = {2108481, 3525347};
const int maxn = 2005;
ll pb[maxn][k], ipb[maxn][k];

ll ex(ll a, ll b, ll c) {
    ll ans = 1;
    while(b) {
        if(b&1) ans = ans * a % c;
        b >>= 1;
        a = a * a % c;
    }
    return ans;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    for(int j = 0; j < k; j++)
        pb[0][j] = 1;

    for(int j = 0; j < k; j++) {
        for(int i = 1; i < maxn; i++) {
            pb[i][j] = (pb[i-1][j] * b[j]) % mod;
        }
    }

    for(int j = 0; j < k; j++) {
        ipb[0][j] = 1;
        ipb[1][j] = ex(pb[1][j], mod-2, mod);
    }

    for(int j = 0; j < k; j++) {
        for(int i = 2; i < maxn; i++) {
            ipb[i][j] = (ipb[i-1][j] * ipb[1][j]) % mod;
        }
    }

    string t, s, e; cin >> t >> s >> e;

    ll ht[t.size()][k];
    for(int j = 0; j < k; j++) {
        ht[0][j] = t[0] - 'a' + 1;
    }

    for(int j = 0; j < k; j++) {
        for(int i = 1; i < (int) t.size(); i++) {
            ht[i][j] = (ht[i-1][j] + (t[i]-'a'+1) * pb[i][j]) % mod;
        }
    }

    vector<ll> h(k, 0);
    auto get_hash = [&](const string& x) {
        h[0] = h[1] = 0;

        for(int j = 0; j < k; j++) {
            for(int i = 0; i < (int) x.size(); i++) {
                h[j] = (h[j] + (x[i]-'a'+1) * pb[i][j]) % mod;
            }
        }
        return (ll(h[0]) << 32) + h[1];
    };

    vector<ll> ans(k);
    auto get_range = [&](int l, int r) {
        ans[0] = ans[1] = 0;
        for(int j = 0; j < k; j++) {
            if(l == 0) ans[j] = ht[r][j];
            else ans[j] = (ht[r][j]-ht[l-1][j]) * ipb[l][j] % mod;

            if(ans[j] < 0) ans[j] += mod;
        }
        return (ll(ans[0]) << 32) + ans[1];
    };

    ll hs = get_hash(s), he = get_hash(e);

    vector<ll> qwe;
    int n = t.size();
    vi L(n, 0), R(n, 0);

    for(int i = 0; i < n; i++) {
        if(i + (int) s.size() - 1 < n) {
            int j = i + s.size() - 1;
            if(get_range(i, j) == hs) L[i] = 1;
        }
        if(i + (int) e.size() - 1 < n) {
            int j = i + e.size() - 1;
            if(get_range(i, j) == he) R[i] = 1;
        }
    }

    //for(int i = 0; i < n; i++) {
        //cout << L[i] << " " << R[i] << "\n";
    //}

    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            if(L[i] == 1 and R[j] == 1 and i + (int) s.size() <= j + (int) e.size()) {
                ll ans = get_range(i, j + (int) e.size() - 1);
                qwe.pb(ans);
            }
        }
    }

    sort(all(qwe));
    qwe.erase(unique(all(qwe)), qwe.end());

    cout << qwe.size() << "\n";
	
    return 0;
}