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

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