結果

問題 No.515 典型LCP
ユーザー pekempeypekempey
提出日時 2017-09-13 22:56:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 542 ms / 1,000 ms
コード長 5,268 bytes
コンパイル時間 2,965 ms
コンパイル使用メモリ 222,220 KB
実行使用メモリ 93,960 KB
最終ジャッジ日時 2024-11-07 20:08:19
合計ジャッジ時間 8,746 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 542 ms
91,700 KB
testcase_01 AC 402 ms
92,192 KB
testcase_02 AC 239 ms
87,636 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 286 ms
93,924 KB
testcase_06 AC 287 ms
90,796 KB
testcase_07 AC 293 ms
93,788 KB
testcase_08 AC 312 ms
93,960 KB
testcase_09 AC 195 ms
90,884 KB
testcase_10 AC 194 ms
90,888 KB
testcase_11 AC 193 ms
90,884 KB
testcase_12 AC 194 ms
90,888 KB
testcase_13 AC 195 ms
90,880 KB
testcase_14 AC 139 ms
90,904 KB
testcase_15 AC 293 ms
93,852 KB
testcase_16 AC 289 ms
90,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

class SuffixDataStructure {
public:
  // a[i]>=0
  SuffixDataStructure(const std::vector<int> &a) : a(a) {
    sa = suffix_array(a);
    sa.insert(sa.begin(), a.size());
    build_lcp();
    build_rmq();
  }

  int get_lcp(int i, int j) {
    if (i == j) {
      return a.size() - std::max(i, j);
    }
    i = isa[i];
    j = isa[j];
    if (i > j) {
      std::swap(i, j);
    }
    int k = __lg(j - i);
    // int k = lg[j - i];
    return std::min(rmq[k][i], rmq[k][j - (1 << k)]);
  }

private:
  const std::vector<int> &a;
  std::vector<int> sa;
  std::vector<int> isa;
  std::vector<int> lcp;
  std::vector<int> lg;
  std::vector<std::vector<int>> rmq;

  vector<int> suffix_array(vector<int> a) {
    const int n = a.size();
    if (n == 0) return {};
    constexpr int TYPE_L = 0, TYPE_S = 1;
    const auto mp = [](vector<int> f, vector<int> a) { for (int &x : a) x = f[x]; return a; };
    const auto filter = [](auto f, vector<int> a) { vector<int> y; for (int &x : a) if (f(x)) y.push_back(x); return y; };
    const auto seq = [](int n) { vector<int> a(n); for (int i = 0; i < n; i++) a[i] = i; return a; };
    const auto freq = [](vector<int> a) { vector<int> f(*max_element(a.begin(), a.end()) + 1); for (int x : a) f[x]++; return f; };
    const auto tail = [](vector<int> a) { a.erase(a.begin()); return a; };
    const auto pairs = [](vector<int> a) { vector<pair<int, int>> b; for (int i = 0; i + 1 < a.size(); i++) b.emplace_back(a[i], a[i + 1]); return b; };
    const auto scanl = [](auto f, auto acc, auto a) { vector<decltype(acc)> b(a.size() + 1); b.front() = acc; for (int i = 0; i < a.size(); i++) b[i + 1] = acc = f(acc, a[i]); return b; };
    const auto scanr = [](auto f, auto acc, auto a) { vector<decltype(acc)> b(a.size() + 1); b.back() = acc; for (int i = int(a.size()) - 1; i >= 0; i--) b[i] = acc = f(a[i], acc); return b; };
    const auto runl = [](vector<int> &a, auto pred, auto f) { for (int i = 0; i < a.size(); i++) if (pred(a[i])) f(a[i]); };
    const auto runr = [](vector<int> &a, auto pred, auto f) { for (int i = int(a.size()) - 1; i >= 0; i--) if (pred(a[i])) f(a[i]); };
    const auto run_pairs = [](vector<int> a, auto f) { for (int i = 0; i + 1 < a.size(); i++) f(a[i], a[i + 1]); };
    const auto type = scanr([](pair<int, int> a, int acc) { return a.first == a.second ? acc : a.first < a.second; }, TYPE_L, pairs(a));
    const auto induced_sort = [&](vector<int> lms) {
      vector<int> sa(n, -1);
      auto L = scanl([](int a, int b) { return a + b; }, 0, freq(a)), S = tail(L), SS = S;
      sa[L[a.back()]++] = n - 1;
      auto is_type_l = [&](int k) { return k > 0 && type[k - 1] == TYPE_L; };
      auto is_type_r = [&](int k) { return k > 0 && type[k - 1] == TYPE_S; };
      runr(lms, [](int x) { return true; }, [&](int i) { sa[--SS[a[i]]] = i; });
      runl(sa, is_type_l, [&](int i) { sa[L[a[i - 1]]++] = i - 1; });
      runr(sa, is_type_r, [&](int i) { sa[--S[a[i - 1]]] = i - 1; });
      return sa;
    };
    const auto is_lms = [&](int k) { return k > 0 && type[k - 1] == TYPE_L && type[k] == TYPE_S; };
    const auto lms = filter(is_lms, seq(n));
    const auto next = scanr([is_lms](pair<int, int> a, int acc) { return is_lms(a.second) ? a.second : acc; }, n, pairs(seq(n)));
    const auto cmp = [&a, &next](int i, int j) { return lexicographical_compare(a.begin() + i, a.begin() + next[i], a.begin() + j, a.begin() + next[j]); };
    vector<int> rank(n);
    run_pairs(filter(is_lms, induced_sort(lms)), [&](int i, int j) { rank[j] = rank[i] + cmp(i, j); });
    return induced_sort(mp(lms, suffix_array(mp(rank, lms))));
  }

  void build_lcp() {
    const int n = a.size();
    isa.resize(n + 1);
    lcp.assign(n + 1, 0);
    for (int i = 0; i <= n; i++) {
      isa[sa[i]] = i;
    }
    int k = 0;
    for (int i = 0; i < n; i++) {
      int j = sa[isa[i] - 1];
      k = std::max(0, k - 1);
      while (i + k < n && j + k < n && a[i + k] == a[j + k]) {
        k++;
      }
      lcp[isa[i] - 1] = k;
    }
  }

  void build_rmq() {
    const int n = lcp.size();
    lg.resize(n + 1);
    for (int i = 2; i <= n; i++) {
      lg[i] = lg[i / 2] + 1;
    }
    const int m = lg[n];
    rmq.assign(m + 1, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
      rmq[0][i] = lcp[i];
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j + (1 << i) < n; j++) {
        rmq[i + 1][j] = std::min(rmq[i][j], rmq[i][j + (1 << i)]);
      }
    }
  }
};

int main() {
  int n;
  cin >> n;

  std::vector<int> start(n);
  std::vector<int> t;
  std::vector<int> len(n);
  for (int i = 0; i < n; i++) {
    start[i] = t.size();
    static char buf[800001];
    scanf("%s", buf);
    int j;
    for (j = 0; buf[j] != 0; j++) {
      t.push_back(buf[j]);
    }
    len[i] = j;
  }

  SuffixDataStructure suf(t);

  int m;
  long long x, d;
  cin >> m >> x >> d;

  long long ans = 0;
  const long long N = 1LL * n * (n - 1);
  while (m--) {
    int i = x / (n - 1);
    int j = x % (n - 1);
    if (i > j) {
      std::swap(i, j);
    } else {
      j = j + 1;
    }
    x += d;
    if (x >= N) {
      x -= N;
    }
    ans += min(suf.get_lcp(start[i], start[j]), min(len[i], len[j]));
  }
  std::cout << ans << std::endl;
}
0