[Blog] [Docs] [Code] [Slides] [About]

KickStart 2020 Round A-D Bundling

字典树hashing

2020-03-26 16:37 CST

Problem

将$N$个字符串分为$K$个一组,使得每组的最长公共前缀长度之和最大。

官方参考解法是用字典树存放字符串(很直观),然而我忘了有这个数据结构,用优先队列+滚动哈希xjb过了。

Solution

#include <iostream>
#include <map>
#include <string>
#include <queue>
using namespace std;

const long long base = 31LL;
const long long mod = 1000000007LL;
const long long rev = 129032259LL;

int n = 0, k = 0;
string s[100005];

class Node {
public:
  int len, cnt, str;
  long long hash;
  explicit Node(int str) : str(str) {
    len = s[str].size(), cnt = 1;
    hash = 0LL;
    for (int i = 0; i < len; ++i) {
      hash = (hash * base + (s[str][i] - 'A')) % mod;
    }
  }
  Node(int len, int cnt, int str, long long hash)
    : len(len), cnt(cnt), str(str), hash(hash) {}
  bool operator<(const Node &rhs) const {
    return len < rhs.len or (len == rhs.len and hash < rhs.hash);
  }
};
priority_queue<Node> pq;

long long findAns() {
  long long ans = 0;
  while (!pq.empty()) {
    auto t = pq.top();
    pq.pop();
    int cnt = t.cnt;
    while (!pq.empty() and t.len == pq.top().len and t.hash == pq.top().hash) {
      cnt += pq.top().cnt;
      pq.pop();
    }
    if (cnt >= k) {
      ans += (long long)t.len * (cnt / k);
      cnt %= k;
    }
    if (cnt > 0 and t.len > 1) {
      long long hash = ((t.hash - (s[t.str][t.len-1] - 'A') + mod) % mod) * rev % mod;
      pq.emplace(Node(t.len-1, cnt, t.str, hash));
    }
  }
  return ans;
}

int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int T = 0;
  cin >> T;
  for (int t = 1; t <= T; ++t) {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
      cin >> s[i];
      pq.emplace(Node(i));
    }
    cout << "Case #" << t << ": " << findAns() << endl;
  }
}     
<EOF>