2022/round3/second_mistake.cpp

#include <chrono>
#include <iostream>
#include <unordered_map>
using namespace std;

const string ALPHA = "meta";

using LL = long long;
const LL MOD = (1LL << 62) - 57;
const LL SEED = chrono::steady_clock::now().time_since_epoch().count();

LL get_hash(LL v) {
  unsigned long long x = v + SEED;
  // http://xorshift.di.unimi.it/splitmix64.c
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return (x ^ (x >> 31)) % MOD;
}

LL add(LL a, LL b) { return (a % MOD + b % MOD) % MOD; }
LL sub(LL a, LL b) { return ((a - b) % MOD + MOD) % MOD; }

LL hash_idx(int i, char c) {
  return get_hash(get_hash(i) + (c - 'a'));
}

LL hash_str(const string &s) {
  LL res = 0;
  for (int i = 0; i < (int)s.size(); i++) {
    res = add(res, hash_idx(i, s[i]));
  }
  return res;
}

// Updates hash for index i from old_c to new_c.
LL swap_char(LL h, int i, char old_c, int new_c) {
  return add(sub(h, hash_idx(i, old_c)), hash_idx(i, new_c));;
}

long long solve() {
  int N, Q;
  string V, W;
  cin >> N;
  // H[h][j] = # of words in V that swapping jth char yields hash h.
  // Htot[h] = total # of words in V that swapping the jth char gets hash h.
  unordered_map<LL, unordered_map<int, int>> H;
  unordered_map<LL, int> Htot;
  for (int i = 0; i < N; i++) {
    cin >> V;
    LL h = hash_str(V);
    for (int j = 0; j < (int)V.size(); j++) {
      for (char c : ALPHA) {
        if (V[j] != c) {
          LL h2 = swap_char(h, j, V[j], c);
          H[h2][j]++;
          Htot[h2]++;
        }
      }
    }
  }
  LL ans = 0;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    cin >> W;
    LL h = hash_str(W);
    for (int j = 0; j < (int)W.size(); j++) {
      for (char c : ALPHA) {
        if (W[j] != c) {
          LL h2 = swap_char(h, j, W[j], c);
          ans += Htot[h2] - H[h2][j];
        }
      }
    }
  }
  return ans / 2;  // Remove double counting of order of 2 indices swapped.
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}