Submission #1611315

---

Source Code Expand

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    vector<vector<int>> next(n, vector<int>(26, n + 10));
    vector<vector<int>> prev(n, vector<int>(26, -1));
    vector<int> fir(26, n + 10);
    int q;
    cin >> q;
    for (int i = 0; i < n; ++i) {
        fir[s[i] - 'a'] = min(fir[s[i] - 'a'], i);
        for (int j = i - 1; j >= 0; --j) {
            next[j][s[i] - 'a'] = i;
            if (s[j] == s[i]) break;
        }
        for (int j = i + 1; j < n; ++j) {
            prev[j][s[i] - 'a'] = i;
            if (s[j] == s[i]) break;
        }
    }
    for (int i = 0; i < q; ++i) {
        string t;
        cin >> t;
        int m = t.length();
        int r = fir[t[0] - 'a'], l;
        if (r >= n) {
            cout << -1 << "\n";
            continue;
        }
        for (int j = 1; j < m; ++j) {
            r = next[r][t[j] - 'a'];
            if (r >= n) {
                cout << -1 << "\n";
                goto A;
            }
        }
        l = r;
        for (int j = m - 2; j >= 0; --j) {
            l = prev[l][t[j] - 'a'];
        }
        cout << l + 1 << " " << r + 1 << "\n";
        A:
        continue;
    }
    return 0;
}

Submission Info

Judge Result