読者です 読者をやめる 読者になる 読者になる

Japan Alumni Group Summer Camp 2014 Day 4 F: Longest Match (SA-IS)

AtCoder 競技プログラミング

kenkoooo.hatenablog.com

hirokazu さんの SA-IS ライブラリをコピペさせてもらった。

コード

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

class SuffixArrayIS {
  string text;

 public:
  vector<int> sa;

 private:
  static bool eq(const vector<int> &v, int idx1, int idx2,
                 const vector<bool> &type) {
    if (v[idx1] != v[idx2]) return false;
    int end = v.size() - 1;
    for (int i = 1;; i++) {
      if (v[idx1 + i] != v[idx2 + i]) return false;
      if (idx1 + i == end || (type[idx1 + i - 1] && !type[idx1 + i]))
        return idx2 + i == end || (type[idx2 + i - 1] && !type[idx2 + i]);
      else if (idx2 + i == end || (type[idx2 + i - 1] && !type[idx2 + i]))
        return false;
    }
    return true;
  }
  template <bool erase>
  static inline void Lsort(const vector<int> &v, const vector<bool> &type,
                           vector<int> &bucket, vector<int> &rank_less) {
    for (int i = 0; i < (int)bucket.size(); i++) {
      if (bucket[i] > 0 && type[bucket[i] - 1]) {
        bucket[rank_less[v[bucket[i] - 1]]++] = bucket[i] - 1;
        if (erase) bucket[i] = -1;
      }
    }
  }
  template <bool erase>
  static inline void Ssort(const vector<int> &v, const vector<bool> &type,
                           vector<int> &bucket, vector<int> &rank_less_eq) {
    for (int i = bucket.size() - 1; i >= 0; i--) {
      if (bucket[i] > 0 && !type[bucket[i] - 1]) {
        bucket[--rank_less_eq[v[bucket[i] - 1]]] = bucket[i] - 1;
        if (erase) bucket[i] = -1;
      }
    }
  }

  static vector<int> induced_sorting(const vector<int> &v, int alpha) {
    vector<int> bucket(v.size());
    vector<int> rank(alpha), c(alpha);
    vector<bool> type(v.size());  // false=>S,true=>L
    vector<int> lmsidx, lmsord;
    type.back() = true;
    for (int i = v.size() - 2; i >= 0; i--) {
      if (v[i] < v[i + 1])
        type[i] = false;
      else if (v[i] > v[i + 1])
        type[i] = true;
      else
        type[i] = type[i + 1];
    }
    for (int i = 0; i < (int)v.size(); i++) rank[v[i]]++;
    for (int i = 1; i < alpha; i++) rank[i] += rank[i - 1];

    // sorting LMS-substring
    fill(bucket.begin(), bucket.end(), -1);
    int lmscnt = 0, idx = -1;
    copy(rank.begin(), rank.end(), c.begin());
    for (int i = 1; i < (int)v.size(); i++) {
      if (type[i - 1] && !type[i]) {  // LMS
        if (lmscnt++) bucket[--c[v[i]]] = i;
        idx = i;
      }
    }
    if (2 <= lmscnt) {
      copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);
      c[0] = 0;
      bucket[c[v.back()]++] = v.size() - 1;
      Lsort<true>(v, type, bucket, c);
      copy(rank.begin(), rank.end(), c.begin());
      Ssort<true>(v, type, bucket, c);
      for (int i = 0; i < (int)bucket.size(); i++)
        if (bucket[i] > 0) lmsidx.push_back(bucket[i]);
      if (!lmsidx.empty()) {
        lmsord.resize(lmsidx.size());
        lmsord[0] = 0;
        for (int i = 1; i < (int)lmsidx.size(); i++) {
          if (eq(v, lmsidx[i - 1], lmsidx[i], type))
            lmsord[i] = lmsord[i - 1];
          else
            lmsord[i] = lmsord[i - 1] + 1;
        }
        if (lmsord.back() + 1 != lmsord.size()) {
          vector<int> lmssuffix;
          fill(bucket.begin(), bucket.end(), -1);
          for (int i = 0; i < (int)lmsidx.size(); i++) {
            if (lmsidx[i]) bucket[lmsidx[i]] = lmsord[i];
          }
          lmsidx.clear();
          for (int i = 0; i < (int)bucket.size(); i++) {
            if (bucket[i] != -1) {
              lmssuffix.push_back(bucket[i]);
              lmsidx.push_back(i);
            }
          }
          vector<int> lmssa(induced_sorting(lmssuffix, lmsord.back() + 1));
          for (int i = 0; i < (int)lmsidx.size(); i++) {
            lmsord[i] = lmsidx[lmssa[i]];
          }
          lmsidx.swap(lmsord);
        }
        lmsord.clear();
      }
    } else if (1 == lmscnt) {
      lmsidx.push_back(idx);
    }
    // ended sorting LMS-substring
    fill(bucket.begin(), bucket.end(), -1);
    copy(rank.begin(), rank.end(), c.begin());
    for (int i = lmsidx.size() - 1; i >= 0; i--)
      bucket[--c[v[lmsidx[i]]]] = lmsidx[i];
    copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1);
    c[0] = 0;
    bucket[c[v.back()]++] = v.size() - 1;
    Lsort<false>(v, type, bucket, c);
    copy(rank.begin(), rank.end(), c.begin());
    Ssort<false>(v, type, bucket, c);
    return bucket;
  }

 public:
  SuffixArrayIS(const string &s) { build(s); }
  const string &get_text() const { return text; }
  void build(const string &s) {
    text = s;
    vector<int> v(s.size());
    for (int i = 0; i < (int)s.size(); i++) v[i] = s[i] - 'a';
    sa = induced_sorting(v, 26);
  }

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

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

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

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

  string S;
  cin >> S;
  int N = S.size();
  SuffixArrayIS 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]);
  }
  cerr << sa.sa << endl;

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