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;
}