615C - Running Track - CodeForces Solution

#include <bits/stdc++.h>
// AC2#
using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define fi first
#define se second
#define pb push_back
#define SZ(x) int((x).size())
#define ALL(x) begin(x), end(x)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ENDL '\n'

void buildPi(string& p, vi& pi) {
    pi = vi(SZ(p));
    int k = -2;
    FOR(i, 0, SZ(p)) {
        while (k >= -1 && p[k + 1] != p[i])
            k = (k == -1) ? -2 : pi[k];
        pi[i] = ++k;
    }
}

pi kmp(string& t, string& p) {
    if (p == "")
        return {0, 0};

    vi pi;
    buildPi(p, pi);
    int k = -1;
    FOR(i, 0, SZ(t)) {
        while (k >= -1 && p[k + 1] != t[i])
            k = (k == -1) ? -2 : pi[k];
        k++;
        if (k == SZ(p) - 1) {
            return {i - k, i - k + SZ(p) - 1};
        }
    }
    return {-1, -1};
}

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

    string s, t;
    cin >> s >> t;
    string s_i = s;
    reverse(ALL(s_i));

    vector<bool> in_s(SZ(s), 0);
    FOR(i, 0, SZ(s)) {
        in_s[s[i] - 'a'] = 1;
    }

    FOR(i, 0, SZ(t)) {
        if (!in_s[t[i] - 'a']) {
            cout << -1 << ENDL;
            return 0;
        }
    }

    t += '#';

    int ind = 0;
    vector<pi> coatings;
    while (ind < SZ(t) - 1) {
        string aux = "";
        int last_l, last_r;
        while (1) {
            auto [l1, r1] = kmp(s, aux);
            auto [l2, r2] = kmp(s_i, aux);

            if (l1 != -1) {
                last_l = l1;
                last_r = r1;
            } else if (l2 != -1) {
                last_l = SZ(s) - l2 - 1;
                last_r = SZ(s) - r2 - 1;
            }

            if (l1 == -1 && l2 == -1) {
                ind--;
                coatings.pb({last_l + 1, last_r + 1});
                break;
            }
            aux += t[ind++];
        }
    }

    cout << SZ(coatings) << ENDL;
    for (auto& [u, v] : coatings)
        cout << u << ' ' << v << ENDL;
    return 0;
}