ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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) {
add.push_back((i == rows - 1 ? '\0' : '\n'));
}
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;
}