UVa12338

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はスパソ式。

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4. #include <set>  
5. #include <map>  
6. #include <queue>  
7. #include <stack>  
8.   
9. #include <cstdio>  
10. #include <cstring>  
11. #include <cstdlib>  
12. #include <cmath>  
13.   
14. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
15. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
16. #define ALL(c) (c).begin(),(c).end()  
17.   
18. typedef long long int lli;  
19.   
20. using namespace std;  
21.   
22. class RMQ {  
23. public:  
24.   int *n, size;  
25.   RMQ()  
26.   {  
27.     n = NULL;  
28.   }  
29.   RMQ(int a[], int s)  
30.   {  
31.     build(a, s);  
32.   }  
33.   void build(int a[], int s)  
34.   {  
35.     int lg = 1;  
36.     size = s;  
37.     for (int i = 1; i < s; i *= 2) ++lg;  
38.     int *m = n = new int[s * lg];  
39.     copy(a, a + s, m);  
40.     for (int i = 1; i  <s; i *= 2) {  
41.       copy(m, m + s, m + s);  
42.       m += s;  
43.       REP (j, s - i) m[j] = min(m[j], m[j + i]);  
44.     }  
45.     return ;  
46.   }  
47.   int query(int b, int e)  
48.   {  
49.     if (e < b) swap(e, b);  
50.     int k;  
51.     for (k = 0; (1 << (k + 1)) <= (e - b + 1); ++k) ;  
52.     return min(n[b + size * k], n[e + size * k - (1 << k) + 1]);  
53.   }  
54. };  
55.   
56. int main(int argc, char *argv[])  
57. {  
58.   int tc;  
59.   cin >> tc;  
60.   while (tc--) {  
61.     int n;  
62.     cin >> n;  
63.     vector< pair<string, int> > v(n);  
64.     for (int i = 0; i < n; ++i) {  
65.       cin >> v[i].first;  
66.       v[i].second = i;  
67.     }  
68.     sort(v.begin(), v.end());  
69.   
70.     int h[n];  
71.     for (int i = 0; i + 1 < n; ++i) {  
72.       h[i] = 0;  
73.       for (int j = 0; j < min(v[i].first.size(), v[i+1].first.size()); ++j) {  
74.         if (v[i].first[j] != v[i + 1].first[j]) break;  
75.         ++h[i];  
76.       }  
77.     }  
78.   
79.     RMQ rmq(h, n-1);  
80.   
81.     int ord[n];  
82.     for (int i = 0; i < n; ++i) {  
83.       ord[v[i].second] = i;  
84.     }  
85.   
86.     static int cnt = 0;  
87.     cout << "Case " << ++cnt << ":" << endl;  
88.     int q, a, b;  
89.     cin >> q;  
90.     while (q--) {  
91.       cin >> a >> b;  
92.       --a;  
93.       --b;  
94.       if (a == b) cout << v[ord[a]].first.size() << endl;  
95.       else {  
96.         if (ord[a] > ord[b]) swap(a, b);  
97.         cout << rmq.query(ord[a], ord[b] - 1) << endl;  
98.       }  
99.     }  
100.   
101.   }  
102.   return 0;  
103. }  

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