Problem: second_mistake (2022 round3)

You, a perfect speller, have a vocabulary of \(N\) distinct words, \(V_1, ..., V_N\), each consisting of exactly \(L\) lowercase letters from the alphabet \(\{\)`'m'`, `'e'`, `'t'`, `'a'`\(\}\).

Your friend, a truely terrable speler, has attempted to write \(Q\) of these words as \(W_1, ..., W_Q\), each also consisting of \(L\) lowercase letters from the same alphabet.

Let \(S_i\) be the number of words in your vocabulary that differ from \(W_i\) at exactly two indices. Please determine the sum \(S_1 + ... + S_Q\).

# Constraints

\(1 \le T \le 95\)
\(1 \le N, Q \le 750{,}000\)
\(1 \le L = |V_i| = |W_i| \le 20{,}000\)
\((N+Q)*L \le 15{,}000{,}000\)
\(V_{ij} \in \{\)`'m'`, `'e'`, `'t'`, `'a'`\(\}\)
\(W_{ij} \in \{\)`'m'`, `'e'`, `'t'`, `'a'`\(\}\)
All \(V_i\) in a given test case are distinct.

The sum of lengths of all strings across all cases is at most \(18{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains the string \(V_i\). Then, there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains the string \(W_i\).


# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the sum \(S_1 + ... + S_Q\).


# Sample Explanation

The first case is depicted below:

{{PHOTO_ID:1332823754208247|WIDTH:500}}

The answer is \(4\), since:
- \(W_1\) = "`teammate`" differs from "`metamate`" at three indices, so \(S_1 = 0\).
- \(W_2\) = "`meatmate`" differs from "`metamate`" at exactly two indices, so \(S_2 = 1\).
- \(W_3\) = "`metatame`" differs from "`metamate`" at exactly two indices, so \(S_3 = 1\).
- \(W_4\) = "`mememate`" differs from "`metamate`" at exactly two indices, so \(S_4 = 1\).
- \(W_5\) = "`metameme`" differs from "`metamate`" at exactly two indices, so \(S_5 = 1\).

In the second case, the answer is \(0\), since:
- \(W_1\) = "`tata`" differs from \(V_1\) = "`meet`" at four indices, \(V_2\) = "`emma`" at three indices, and \(V_3\) = "`tate`" at only one index, so \(S_1 = 0\).
- \(W_2\) = "`maam`" differs from \(V_1\) = "`meet`" at three indices, \(V_2\) = "`emma`" at four indices, and \(V_3\) = "`tate`" at three indices, so \(S_2 = 0\).

In the third case, the answer is \(5\), since:
- \(W_1\) = "`tam`" differs from both \(V_1\) = "`mem`" and \(V_3\) = "`mat`" at exactly two indices, so \(S_1 = 2\).
- \(W_2\) = "`mat`" differs from \(V_1\) = "`mem`" at exactly two indices, so \(S_2 = 1\).
- \(W_3\) = "`tea`" differs from both \(V_1\) = "`mem`" and \(V_2\) = "met" at exactly two indices, so \(S_3 = 2\).


Sample input:
3
1
metamate
5
teammate
meatmate
metatame
mememate
metameme
3
meet
emma
tate
2
tata
maam
3
mem
met
mat
3
tam
mat
tea


Sample output:
Case #1: 4
Case #2: 0
Case #3: 5


Solution: For each vocabulary word \(V_i\), we can consider changing each letter to every other letter. This gives us \(3*L\) possibilities for words differing by exactly one letter. We can store a hash of each of these "\(1\)-mistaken" strings in a map. 

To avoid an \(\mathcal{O}(L)\) time factor for hashing each possibility, we can use a rolling hash. For example, to hash an array \(A_{1..L}\), we can define \(h(A_1, ..., A_L) := (A_1 * p^1 + ... + A_L* p^L) \text{ mod } P\), where \(p\) and \(P\) are prime numbers. We can then precompute modded prefix sums in \(\mathcal{O}(L\)\). Given any \(h(A_1, ..., A_L)\), we will be able to to replace a value \(A_i\) with \(A_i'\) without rehashing, by computing \((h(A_1, ..., A_L) - h(A_1, ..., A_{i}) + h(A_1, ..., A_{i - 1}) + A_i' * p^i) \text{ mod } P\) in \(O(1)\) time (where the second and third terms are prefix sums).

For each hash \(h\), we can compute two tables of counts:
* \(\text{H}[h][j]\) storing the number of \(1\)-mistaken strings with hash \(h\), mistaken at index \(j\)
* \(\text{Hsum}[h] = \sum_j H[h][j]\) storing the total number of \(1\)-mistaken strings with hash \(h\)

For each query \(W_i\), we can first compute \(h(W_i\)) in \(\mathcal{O}(L)\). Then, we can go through all \(3*L\) possibilities of strings derived from swapping \(W_i\) at each index \(j_1\) (deriving a new hash \(h'\) from \(h(W_i)\) in \(\mathcal{O}(1)\) time as described above). We can see if this swap matches any previously \(1\)-mistaken strings (mistake at some other index \(j_2\)). Each such replacement will contribute \((\text{Hsum}[h'] - \text{H}[h'][j_1])/2\) to the answer. That is, we need to exclude hashes where \(j_1\) equals a previously-mistaken index, and divide by \(2\) to avoid double counting \((j_1, j_2)\) and \((j_2, j_1)\).

The overall time and space complexity is \(\mathcal{O}{(3*L*(N + Q))}\).


Code: #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;
}