Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match

問題

RUPC 2016 の時に @public_sate さんに教えてもらった。

F: Longest Match - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder

解法

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <class T, class U>
void chmin(T &t, U f) {
  if (t > f) t = f;
}
template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

struct RMQ {
  static const int N = 1 << 20;
  vector<long long> seg;
  RMQ() : seg(N * 2, (long long)1e18) {}

  void update(int k, long long value) {
    seg[k += N - 1] = value;
    while (k > 0) {
      k = (k - 1) / 2;
      seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }

  //[a, b)
  long long query(int a, int b, int k = 0, int l = 0, int r = N) {
    if (r <= a || b <= l) return 1e18;
    if (a <= l && r <= b) return seg[k];
    long long x = query(a, b, k * 2 + 1, l, (l + r) / 2);
    long long y = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(x, y);
  }
};

class SuffixArray {
 private:
  string s;
  SuffixArray() {}

 public:
  vector<int> sa;
  SuffixArray(string const &s) {
    this->s = s;
    sa.resize(s.size() + 1);
    build();
  }

  void build() {
    int n = s.length();
    vector<int> rank(n + 1);
    for (int i = 0; i < n + 1; ++i) {
      sa[i] = i;
      rank[i] = i < n ? s[i] : -1;
    }

    for (int k = 1; k <= n; k *= 2) {
      auto compare = [&](int i, int j) {
        int ri = i + k <= n ? rank[i + k] : -1;
        int rj = j + k <= n ? rank[j + k] : -1;
        return make_pair(rank[i], ri) < make_pair(rank[j], rj);
      };
      sort(sa.begin(), sa.end(), compare);
      vector<int> dp(n + 1);
      dp[sa[0]] = 0;
      for (int i = 0; i < n; ++i)
        dp[sa[i + 1]] = dp[sa[i]] + compare(sa[i], sa[i + 1]);
      rank = dp;
    }
    sa.erase(sa.begin());
  }

  int lower_bound(const string &t) {
    int a = -1, b = s.size() - 1;
    while (b - a > 1) {
      int c = (a + b) / 2;
      if (s.compare(sa[c], t.size(), t) < 0)
        a = c;
      else
        b = c;
    }
    return s.compare(sa[b], t.size(), t) == 0 ? b : -1;
  }

  int upper_bound(const string &t) {
    int a = -1, b = s.size();
    while (b - a > 1) {
      int c = (a + b) / 2;
      if (s.compare(sa[c], t.size(), t) <= 0)
        a = c;
      else
        b = c;
    }
    return b;
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string S;
  cin >> S;
  int N = S.size();
  SuffixArray sa(S), revsa(string(S.rbegin(), S.rend()));

  RMQ rmq, rev;
  for (int i = 0; i < N; i++) {
    rmq.update(i, sa.sa[i]);
    rev.update(i, revsa.sa[i]);
  }

  int M;
  cin >> M;
  while (M--) {
    string x, y;
    cin >> x >> y;
    reverse(y.begin(), y.end());

    int low = sa.lower_bound(x);
    if (low == -1) {
      cout << 0 << endl;
      continue;
    }
    int up = sa.upper_bound(x);

    int rlow = revsa.lower_bound(y);
    if (rlow == -1) {
      cout << 0 << endl;
      continue;
    }
    int rup = revsa.upper_bound(y);

    int s = rmq.query(low, up);
    int t = N - rev.query(rlow, rup);
    if (s + x.size() <= t && s <= t - y.size()) {
      cout << t - s << endl;
    } else {
      cout << 0 << endl;
    }
  }
}