ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1269. Obscene Words Filter

WA2 suffix array
Posted by Dan 28 Jun 2019 02:09
Why wa2?
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define vc vector

using namespace std;

vc<int> p;
string s;
int n;
void calcSuffixArray() {
    p.resize(n);
    vc<int> c(n), pn(n), cn(n), k(max(256, n));
    for (char ch : s) {
        k[ch]++;
    }
    partial_sum(k.begin(), k.begin() + 256, k.begin());
    for (int i = 0; i < n; ++i) {
        p[--k[s[i]]] = i;
    }
    int classes = 1;
    c[p[0]] = 0;
    for (int i = 1; i < n; ++i) {
        if (s[p[i - 1]] != s[p[i]]) {
            ++classes;
        }
        c[p[i]] = classes - 1;
    }
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; ++i) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0) {
                pn[i] += n;
            }
        }
        fill(k.begin(), k.begin() + classes, 0);
        for (int i = 0; i < n; ++i) {
            k[c[pn[i]]]++;
        }
        partial_sum(k.begin(), k.begin() + classes, k.begin());
        for (int i = n - 1; i >= 0; --i) {
            p[--k[c[pn[i]]]] = pn[i];
        }
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; ++i) {
            int m1 = (p[i] + (1 << h)) % n, m2 = (p[i - 1] + (1 << h)) % n;
            if (c[p[i]] != c[p[i - 1]] || c[m1] != c[m2]) {
                ++classes;
            }
            cn[p[i]] = classes - 1;
        }
        copy(all(cn), c.begin());
    }
}

const int INF = int(2e9);

struct SegTree {
    vc<int> t;

    void build(int v, int l, int r) {
        if (l + 1 == r) {
            t[v] = p[l];
            return;
        }
        int m = (l + r) >> 1;
        int nxt = v + ((m - l) << 1);
        build(v + 1, l, m);
        build(nxt, m, r);
        t[v] = min(t[v + 1], t[nxt]);
    }

    SegTree() {
        t.resize(2 * n);
        build(0, 0, n);
    }

    int getMin(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return t[v];
        }
        int m = (l + r) >> 1;
        int nxt = v + ((m - l) << 1);
        int ans = INF;
        if (ql < m) {
            ans = min(ans, getMin(v + 1, l, m, ql, qr));
        }
        if (m < qr) {
            ans = min(ans, getMin(nxt, m, r, ql, qr));
        }
        return ans;
    }

};

struct comp {
    string t;
    int pos;
    comp(string t) : t(move(t)), pos(0) {}
    bool operator ()(const int& a, const int& b) {
        if (b == -1) {
            return (pos + a < s.size() ? s[a + pos] < t[pos] : true);
        }
        else {
            return (pos + b < s.size() ? t[pos] < s[b + pos] : false);
        }
    }
};

pair<int, int> equalRange(const string& t) {
    int l = 0, r = n;
    comp c(t);
    for (int i = 0; i < t.size() && l < r; ++i) {
        l = lower_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin();
        r = upper_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin();
        c.pos++;
    }
    return make_pair(l, r);
}

void solve() {
    int w;
    cin >> w;
    vc<string> words(w);
    cin.get();
    for (string& i : words) {
        getline(cin, i);
    }
    int rows;
    cin >> rows;
    cin.get();
    vc<int> sz(rows);
    for (int i = 0; i < rows; ++i) {
        string add;
        getline(cin, add);
        add.push_back((i == rows - 1 ? '\0' : '\n'));
        sz[i] = add.size();
        s += add;
    }
    n = s.size();
    calcSuffixArray();

    SegTree tree;
    int ans = INF;
    for (const string& t : words) {
        auto [l, r] = equalRange(t);
        if (l < r) {
            ans = min(ans, tree.getMin(0, 0, n, l, r));
        }
    }

    if (ans == INF) {
        cout << "Passed";
        return;
    }

    for (int i = 0; i < rows; ++i) {
        if (sz[i] <= ans) {
            ans -= sz[i];
        }
        else {
            cout << i + 1 << ' ' << ans + 1 << endl;
            return;
        }
    }
    cout << "WTF";
}

int main() {
    solve();
    return 0;
}