UVa12238
接尾辞配列ライクなことをやる。
与えられた文字列をソートし、となりあう文字列の一致する最長のプレフィックス (LCP) を求める。
それに RMQ を使ってクエリーを処理する。
A[i] と A[i+1] のプレフィックスが n 文字目まで一致していて、
A[i+1] と A[i+2] のプレフィックスが m 文字目まで一致していれば、
A[i] と A[i+2] は min(n, m) 文字目までのプレフィックスが一致していることになる。
A[j]とA[k]のプレフィックスはRMQ(j, k)文字目まで一致することになる。
このアプローチで実行時間が3秒強。タイムリミットが5秒。
ラディックスソートとか使えばもっと早くなるかも?
RMQはスパソ式。
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #define REP(i, n) for(int i=0; i<(int)n; ++i) #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(),(c).end() typedef long long int lli; using namespace std; class RMQ { public: int *n, size; RMQ() { n = NULL; } RMQ(int a[], int s) { build(a, s); } void build(int a[], int s) { int lg = 1; size = s; for (int i = 1; i < s; i *= 2) ++lg; int *m = n = new int[s * lg]; copy(a, a + s, m); for (int i = 1; i <s; i *= 2) { copy(m, m + s, m + s); m += s; REP (j, s - i) m[j] = min(m[j], m[j + i]); } return ; } int query(int b, int e) { if (e < b) swap(e, b); int k; for (k = 0; (1 << (k + 1)) <= (e - b + 1); ++k) ; return min(n[b + size * k], n[e + size * k - (1 << k) + 1]); } }; int main(int argc, char *argv[]) { int tc; cin >> tc; while (tc--) { int n; cin >> n; vector< pair<string, int> > v(n); for (int i = 0; i < n; ++i) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); int h[n]; for (int i = 0; i + 1 < n; ++i) { h[i] = 0; for (int j = 0; j < min(v[i].first.size(), v[i+1].first.size()); ++j) { if (v[i].first[j] != v[i + 1].first[j]) break; ++h[i]; } } RMQ rmq(h, n-1); int ord[n]; for (int i = 0; i < n; ++i) { ord[v[i].second] = i; } static int cnt = 0; cout << "Case " << ++cnt << ":" << endl; int q, a, b; cin >> q; while (q--) { cin >> a >> b; --a; --b; if (a == b) cout << v[ord[a]].first.size() << endl; else { if (ord[a] > ord[b]) swap(a, b); cout << rmq.query(ord[a], ord[b] - 1) << endl; } } } return 0; }
0 件のコメント :
コメントを投稿