[CF] E. Collapsing Strings - Educational Codeforces Round 159 (Rated for Div. 2)

https://codeforces.com/contest/1902/problem/E

题目大意

给出 $n \ (\le 10^6)$ 个字符串,且 $\sum |S_i| \le 10^6$。两个串的运算 $C(a, b)$ 规则如下:

  1. $a$ 为空则 $C(a, b) = b$
  2. $b$ 为空则 $C(a, b) = a$
  3. 若 $a[|a| - 1] = b[0]$ 即 $a$ 的末尾字符与 $b$ 的开头字符相同则 $C(a, b) = C(a', b')$,$a'$ 为 $a$ 去掉尾字符的串,$b'$ 为 $b$ 去掉首字符的串。
  4. 其他情况:$C(a, b) = a + b$ 即 $a$ 与 $b$ 直接拼接。

问 $\sum_i \sum_j |C(S_i, S_j)|$。

简要题解

考虑枚举串 $s_i$ 相当于我们要知道,$s_i$ 的末尾和多少串的前缀重复。于是思路很直观的把所有串插到字典树里,之后用每个串反着查询减去这部分贡献即可。

复杂度

$T$:$O(\sum(S_i))$

$S$:$O(\sum(S_i))$

代码实现

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename T = char, T Base = 'a', int Sigma = 26,
    size_t PRE_ALLO = 100000>
struct Trie {
  struct TN {
    int ch[Sigma];
    int cnt;
  };
  vector<TN> tn;

  Trie() : tn(2) { tn.reserve(PRE_ALLO); }
  void init() { tn.resize(1); newnode(); }
  int newnode() { tn.emplace_back(); return tn.size() - 1; }

  int append(int o, T c) {
    int cc = c - Base;
    if (!tn[o].ch[cc]) { tn[o].ch[cc] = newnode(); }
    return tn[o].ch[cc];
  }
};
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

void solve() {
  int n; cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }

  Trie trie;

  for (int i = 0; i < n; i++) {
    int u = 1;
    for (char c : s[i]) {
      u = trie.append(u, c);
      trie.tn[u].cnt++;
    }
  }

  LL ans = 0;
  for (int i = 0; i < n; i++) {
    ans += 1LL * n * s[i].length();
  }
  ans *= 2;
  // cerr << ans << '\n';

  for (int i = 0; i < n; i++) {
    int u = 1;
    for (int j = s[i].length() - 1; j >= 0; j--) {
      int c = s[i][j] - 'a';
      if (!trie.tn[u].ch[c]) break;

      u = trie.tn[u].ch[c];

      ans -= trie.tn[u].cnt * 2;
    }
    // cerr << ans << '\n';
  }

  cout << ans << '\n';
}

int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
Prev: [CF] B. Subsequence Update - Codeforces Round 1000 (Div. 2)
Next: [CF] D. Robot Queries - Educational Codeforces Round 159 (Rated for Div. 2)