Language: C++

#include <random>

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<uint64_t, uint64_t>;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

struct XorShift {
  using result_type = uint32_t;
  result_type w = 123456789, x = 362436069, y = 521288629, z = 88675123;
  XorShift(result_type seed = time(nullptr)) {
    w = seed;
    x = w << 13;
    y = (w >> 9) ^ (x << 6);
    z = y >> 7;
  }
  static constexpr result_type min() { return 0; }
  static constexpr result_type max() { return 0x7FFFFFFF; }
  result_type operator()() {
    result_type t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
  }
  result_type rand() {
    result_type t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
  }
  // [min,max] の整数値乱数
  result_type randInt(result_type min = 0, result_type max = 0x7FFFFFFF) {
    return rand() % (max - min + 1) + min;
  }
  // [min,max] の浮動小数点乱数
  double randDouble(double min = 0, double max = 1) {
    return (double)(rand() % 0xFFFF) / 0xFFFF * (max - min) + min;
  }
};

XorShift rnd(114514);

uint64_t b1 = (uint64_t)rnd.randInt(2, 114514),
         b2 = (uint64_t)rnd.randInt(2, 114514);

class RollingHash {
  int n;
  static const uint64_t moda = (uint64_t)1e9 + 7;
  static const uint64_t modb = (uint64_t)1e9 + 9;
  // static const uint64_t b1 = (uint64_t)17, b2 = (uint64_t)19;
  std::vector<uint64_t> a, b, p, q;

 public:
  RollingHash(const std::string &str)
      : n((int)str.size()), a(n + 1, 0), b(n + 1, 0), p(n + 1, 1), q(n + 1, 1) {
    for (int i = 0; i < n; i++) {
      a[i + 1] = (a[i] * b1 + uint64_t(str[i])) % moda;
      b[i + 1] = (b[i] * b2 + uint64_t(str[i])) % modb;
      p[i + 1] = p[i] * b1 % moda;
      q[i + 1] = q[i] * b2 % modb;
    }
  }
  // [l, r) のハッシュ値を取得
  std::pair<uint64_t, uint64_t> query(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    uint64_t h1 = (p[r - l] * a[l] - a[r] + moda) % moda;
    uint64_t h2 = 0;
    //uint64_t h2 = (q[r - l] * b[l] - b[r] + modb) % modb;
    return std::make_pair(h1, h2);
  }
};

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

  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s.begin(), s.end(),
       [](const string &x, const string &y) { return x.size() > y.size(); });
  vector<unordered_map<P, ll>> c_sufs(26);
  vector<ll> c_cnt(26);
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    //cerr << s[i] << endl;
    if (s[i].size() == 1) {
      int idx = s[i][0] - 'a';
      ans += c_cnt[idx];
      c_cnt[idx]++;
      continue;
    }
    vector<int> ok(26);
    for (auto c : s[i]) {
      int idx = c - 'a';
      ok[idx] = 1;
    }
    for (int j = 0; j < 26; j++)
      if (ok[j]) c_cnt[j]++;
    RollingHash rh(s[i]);
    int sz = s[i].size();

    // [][----]
    auto p = rh.query(1, sz);
    int index = s[i][0] - 'a';
    if (c_sufs[index].count(p)) ans += c_sufs[index][p];

    vector<int> cnt(26);
    for (int j = 0; j < sz; j++) {
      int idx = s[i][j] - 'a';
      auto val = rh.query(j, sz);
      //cerr << j << " " << val.first << " " << val.second << endl;
      for (int k = 0; k < 26; k++) {
        if (cnt[k]) c_sufs[k][val]++;
      }
      cnt[idx]++;
    }
  }
  cout << ans << endl;
}


Compiler output:
In file included from /usr/include/c++/14/bits/hashtable.h:35,
                 from /usr/include/c++/14/bits/unordered_map.h:33,
                 from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53,
                 from a.cc:3:
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_M_hash_code(const _Key&) const [with _Key = std::pair<long unsigned int, long unsigned int>; _Value = std::pair<const std::pair<long unsigned int, long unsigned int>, long long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true; __hash_code = long unsigned int]':
/usr/include/c++/14/bits/hashtable_policy.h:838:45:   required from 'std::__detail::_Map_base<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::mapped_type& std::__detail::_Map_base<_Key, std::pair<const _Key, _Val>, _Alloc, std::__detail::_Select1st, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::operator[](const key_type&) [with _Key = std::pair<long unsigned int, long unsigned int>; _Val = long long int; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >; _Equal = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; mapped_type = long long int; key_type = std::pair<long unsigned int, long unsigned int>]'
  838 |       __hash_code __code = __h->_M_hash_code(__k);
      |                            ~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/14/bits/unordered_map.h:988:20:   required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = std::pair<long unsigned int, long unsigned int>; _Tp = long long int; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _Pred = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >; mapped_type = long long int; key_type = std::pair<long unsigned int, long unsigned int>]'
  988 |       { return _M_h[__k]; }
      |                ~~~~^
a.cc:122:55:   required from here
  122 |     if (c_sufs[index].count(p)) ans += c_sufs[index][p];
      |                                                       ^
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: error: static assertion failed: hash function must be invocable with an argument of key type
 1335 |         static_assert(__is_invocable<const _Hash&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1335:23: note: 'std::__is_invocable<const std::hash<std::pair<long unsigned int, long unsigned int> >&, const std::pair<long unsigned int, long unsigned int>&>()' evaluates to false
/usr/include/c++/14/bits/hashtable_policy.h:1337:25: error: no match for call to '(const std::hash<std::pair<long unsigned int, long unsigned int> >) (const std::pair<long unsigned int, long unsigned int>&)'
 1337 |         return _M_hash()(__k);
      |                ~~~~~~~~~^~~~~
In file included from /usr/include/c++/14/bits/alloc_traits.h:33,
                 from /usr/include/c++/14/ext/alloc_traits.h:34,
                 from /usr/include/c++/14/bits/basic_string.h:39,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/random:43,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = unordered_map<pair<long unsigned int, long unsigned int>, long long int>; _Args = {}]':
/usr/include/c++/14/bits/stl_uninitialized.h:643:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int>*; _Size = long unsigned int; bool _TrivialValueType = false]'
  643 |                 std::_Construct(std::__addressof(*__cur));
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:712:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = unordered_map<pair<long unsigned int, long unsigned int>, long long int>*; _Size = long unsigned int]'
  710 |       return __uninitialized_default_n_1<__is_trivial(_ValueType)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  711 |                                          && __can_fill>::
      |                                          ~~~~~~~~~~~~~~~~
  712 |         __uninit_default_n(__first, __n);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:779:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, allocator<_Tp>&) [with _ForwardIterator = unordered_map<pair<long unsigned int, long unsigned int>, long long int>*; _Size = long unsigned int; _Tp = unordered_map<pair<long unsigned int, long unsigned int>, long long int>]'
  779 |     { return std::__uninitialized_default_n(__first, __n); }
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1720:36:   required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(size_type) [with _Tp = std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int>; _Alloc = std::allocator<std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int> >; size_type = long unsigned int]'
 1720 |           std::__uninitialized_default_n_a(this->_M_impl._M_start, __n,
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 1721 |                                            _M_get_Tp_allocator());
      |                                            ~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:558:9:   required from 'std::vector<_Tp, _Alloc>::vector(size_type, const allocator_type&) [with _Tp = std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int>; _Alloc = std::allocator<std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int> >; size_type = long unsigned int; allocator_type = std::allocator<std::unordered_map<std::pair<long unsigned int, long unsigned int>, long long int> >]'
  558 |       { _M_default_initialize(__n); }
      |         ^~~~~~~~~~~~~~~~~~~~~
a.cc:98:41:   required from here
   98 |   vector<unordered_map<P, ll>> c_sufs(26);
      |                                         ^
/usr/include/c++/14/bits/stl_construct.h:119:7: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<long unsigned int, long unsigned int>; _Tp = long long int; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _Pred = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >]'
  119 |       ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:148:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::pair<long unsigned int, long unsigned int>; _Tp = long long int; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _Pred = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >]' is implicitly deleted because the default definition would be ill-formed:
  148 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:148:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<long unsigned int, long unsigned int>; _Value = std::pair<const std::pair<long unsigned int, long unsigned int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
/usr/include/c++/14/bits/hashtable.h:539:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<long unsigned int, long unsigned int>; _Value = std::pair<const std::pair<long unsigned int, long unsigned int>, long long int>; _Alloc = std::allocator<std::pair<const std::pair<long unsigned int, long unsigned int>, long long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::pair<long unsigned int, long unsigned int> >; _Hash = std::hash<std::pair<long unsigned int, long unsigned int> >; _RangeHash = std::__detail