#548406 (C++17) No.515 典型LCP

• 問題: No.515 典型LCP
• ユーザー: Haar
• 提出日時: 2020-09-05 08:47:06
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,151 bytes
• コンパイル時間: 4,359 ms
• コンパイル使用メモリ: 227,124 KB
• 最終ジャッジ日時: 2025-01-14 07:00:58
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 7 TLE * 8

ソースコード

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...)
#endif

/**
 * @title Suffix array
 * @docs suffix_array.md
 */
template <typename Container, typename T = typename Container::value_type>
struct SuffixArray {
  Container s;
  int N;
  std::vector<int> data;

  SuffixArray(Container s): s(s), N(s.size()), data(N){
    if(N == 1){
      data = {1, 0};
      return;
    }

    s.resize(N + 1);

    std::string LS(N + 1, 'S');
    for(int i = N; --i >= 0;){
      if(s[i] < s[i + 1]) LS[i] = 'S';
      else if(s[i] > s[i + 1]) LS[i] = 'L';
      else LS[i] = LS[i + 1];
    }

    const int bucket_count = *std::max_element(s.begin(), s.end());
    std::vector<int> bucket_size(bucket_count + 1);
    for(auto x : s) bucket_size[x] += 1;

    auto induced_sort =
      [&](std::vector<int> LMS){
        std::vector<int> bucket(N + 1, -1);
        std::vector<bool> is_lms(N + 1);

        std::vector<std::deque<int>> empty(bucket_count + 1);

        for(int i = 0, k = 0; i <= bucket_count; ++i){
          for(int j = 0; j < bucket_size[i]; ++j){
            empty[i].push_back(k);
            ++k;
          }
        }

        std::reverse(LMS.begin(), LMS.end());
        for(auto x : LMS){
          int i = empty[s[x]].back(); empty[s[x]].pop_back();

          bucket[i] = x;
          is_lms[i] = true;
        }

        for(int i = 0; i <= N; ++i){
          if(bucket[i] >= 1 and LS[bucket[i] - 1] == 'L'){
            auto x = s[bucket[i] - 1];
            int j = empty[x].front(); empty[x].pop_front();
            bucket[j] = bucket[i] - 1;
          }
        }

        for(int i = 0; i <= N; ++i){
          if(is_lms[i]){
            bucket[i] = -1;
          }
        }

        for(int i = 0, k = 0; i <= bucket_count; ++i){
          empty[i].clear();

          for(int j = 0; j < bucket_size[i]; ++j){
            empty[i].push_back(k);
            ++k;
          }
        }

        for(int i = N; i >= 0; --i){
          if(bucket[i] >= 1 and LS[bucket[i] - 1] == 'S'){
            auto x = s[bucket[i] - 1];
            int j = empty[x].back(); empty[x].pop_back();
            bucket[j] = bucket[i] - 1;
          }
        }

        bucket[0] = N;
        return bucket;
      };

    std::vector<int> LMS;
    for(int i = 1; i <= N; ++i){
      if(LS[i] == 'S' and LS[i - 1] == 'L'){
        LMS.push_back(i);
      }
    }

    std::vector<int> LMS_bucket_length(N + 1, 1);
    for(int i = 0; i < (int)LMS.size() - 1; ++i){
      LMS_bucket_length[LMS[i]] = LMS[i + 1] - LMS[i] + 1;
    }

    auto bucket = induced_sort(LMS);

    std::vector<int> LMS_substr_sorted;
    for(int i : bucket){
      if(i > 0 and LS[i - 1] == 'L' and LS[i] == 'S'){
        LMS_substr_sorted.push_back(i);
      }
    }

    std::vector<int> rank(N + 1);
    rank[LMS_substr_sorted[0]] = 1;

    for(int i = 1, k = 1; i < (int)LMS_substr_sorted.size(); ++i){
      const int x = LMS_substr_sorted[i - 1], y = LMS_substr_sorted[i];

      bool eq = true;
      if(LMS_bucket_length[x] != LMS_bucket_length[y]) eq = false;
      else{
        for(int j = 0; j < LMS_bucket_length[x]; ++j){
          if(s[x + j] != s[y + j]) eq = false;
        }
      }

      if(not eq) ++k;
      rank[y] = k;
    }

    std::vector<int> t;
    for(int i = 0; i <= N; ++i){
      if(rank[i] != 0) t.push_back(rank[i]);
    }

    auto sa = SuffixArray<std::vector<int>>(t).data;

    std::vector<int> LMS_sorted;
    for(int i = 1; i < (int)sa.size(); ++i){
      LMS_sorted.push_back(LMS[sa[i]]);
    }

    data = induced_sort(LMS_sorted);
  }

  int operator[](size_t i) const {return data[i];}
  auto begin() const {return data.begin();}
  auto end() const {return data.end();}
  size_t size() const {return data.size();}
};

/**
 * @title LCP(Longest Common Prefix) array
 * @docs lcp_array.md
 */
template <typename T>
struct LCPArray {
  int n;
  std::vector<int> data, rank;
  LCPArray(const SuffixArray<T> &sa): n(sa.size()), data(n), rank(n){
    for(int i = 0; i < n; ++i) rank[sa[i]] = i;

    int h = 0;
    for(int i = 0; i < n; ++i){
      if(rank[i] == 0) continue;
      int j = sa[rank[i] - 1];

      if(h) --h;
      while(j + h < n and i + h < n){
        if(sa.s[j + h] != sa.s[i + h]) break;
        ++h;
      }

      data[rank[i]] = h;
    }
  }

  int operator[](size_t i) const {return data[i];}
  auto begin() const {return data.begin();}
  auto end() const {return data.end();}
};

/**
 * @title Sparse table
 * @docs sparse_table.md
 */
template <typename Semilattice>
class SparseTable {
  using value_type = typename Semilattice::value_type;
  const static Semilattice S;

  std::vector<std::vector<value_type>> a;
  std::vector<int> log_table;

public:
  template <typename T>
  SparseTable(const std::vector<T> &v){
    int n = v.size();
    int logn = 0;
    while((1 << logn) <= n) ++logn;

    a.assign(n, std::vector<value_type>(logn));
    for(int i = 0; i < n; ++i) a[i][0] = v[i];
    for(int j = 1; j < logn; ++j){
      for(int i = 0; i < n; ++i){
        a[i][j] = S(a[i][j - 1], a[std::min<int>(n - 1, i + (1 << (j - 1)))][j - 1]);
      }
    }

    log_table.assign(n + 1, 0);
    for(int i = 2; i < n + 1; ++i) log_table[i] = log_table[i >> 1] + 1;
  }

  value_type get(int s, int t) const { // [s,t)
    int k = log_table[t - s];
    return S(a[s][k], a[t - (1 << k)][k]);
  }

  value_type get(std::vector<std::pair<int, int>> st) const {
    value_type ret;
    bool t = true;

    for(const auto &p : st){
      if(p.first < p.second){
        if(t){
          ret = get(p.first, p.second);
          t = false;
        }else{
          ret = S(ret, get(p.first, p.second));
        }
      }
    }

    return ret;
  }
};

/**
 * @title Min monoid
 * @docs min.md
 */
template <typename T>
struct MinMonoid {
  using value_type = std::optional<T>;

  value_type operator()() const {return {};}
  value_type operator()(const value_type &a, const value_type &b) const {
    if(not a) return b;
    if(not b) return a;
    return {std::min(*a, *b)};
  }
};


void query(int N, int M, int64_t x, int64_t d, std::function<void(int, int)> f){
  for(int k = 0; k < M; ++k){
    int i = x / (N - 1);
    int j = x % (N - 1);
    if(i > j) std::swap(i, j);
    else j += 1;
    x = (x + d) % (N * (N - 1));

    f(i, j);
  }
}

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

  int N; std::cin >> N;

  std::vector<std::string> s(N);
  for(int i = 0; i < N; ++i) std::cin >> s[i];

  int M; std::cin >> M;
  int64_t x, d; std::cin >> x >> d;

  std::string S;
  std::vector<int> pos(N);
  for(int i = 0; i < N; ++i){
    pos[i] = S.size();
    S += s[i];
    S += "$";
  }

  auto sa = SuffixArray(S);
  auto lcp = LCPArray(sa);
  auto rmq = SparseTable<MinMonoid<int>>(lcp.data);


  int64_t ans = 0;
  query(N, M, x, d,
        [&](int i, int j){
          int a = lcp.rank[pos[i]];
          int b = lcp.rank[pos[j]];
          if(a > b) std::swap(a, b);
          auto res = rmq.get(a + 1, b + 1);
          ans += std::min({*res, (int)s[i].size(), (int)s[j].size()});
        }
  );

  std::cout << ans << "\n";

  return 0;
}