题意：两个字符串相似定义为：

1.两个字符串长度相等

2.两个字符串对应位置上至多有一个位置所对应的字符不相同

给定一个字符串\(s\)，\(T\)次询问两个子串在给定的规则下是否相似。给定的规则指每次给出一些等价关系，如‘a'=’b'，‘b'=’c'（具有传递性）

\(|s|,T \leq 3 \times 10^5\)

题目中的每次询问相当于把一些字符合并成了一些联通块，每个联通块内的字符视为相同。这用并查集合并。

首先考虑询问相等而非相似怎么做。直接的子串对比我们可以直接比较哈希值，但这里要支持合并字符。因此，考虑每个字符对哈希值的贡献。把它除以这个字符的权值后，就相当于这个字符在子串中的出现位置的哈希值，在每个联通块内，这是可以直接相加的。因此，我们只要比较两个子串每个联通块的出现位置是否相同，就能判断是否相等。

再考虑恰好有一位不同的情况。在这种情况下，只有两个联通块在两个子串中出现位置不同，且其哈希值的差值为哈希底数的若干次幂及其相反数。这是可以\(O(1)\)判断的。

时间复杂度\(O((|s| + T )\times26)\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 300010, BAS = 233, MOD = 998244353;

char s[N],t[10];

int has[26][N],n,m,pw[N],uni[30],val[2][30],rec[2],cnt;

int getfa(int pos) {

  return pos == uni[pos] ? pos : uni[pos] = getfa(uni[pos]);

}

unordered_map<int,int> mp;

int gethas(int k,int l,int r) {

  return ((has[k][r] - 1ll * has[k][l-1] * pw[r-l+1] % MOD) + MOD) % MOD;

}

void init() {

  for (int i = 1 ; i <= 26 ; ++ i)

    uni[i] = i;

  memset(val,0,sizeof val);

  cnt = 0;

}

void solve() {

  int k,l1,r1,l2,r2,x,y;

  scanf("%d%d%d%d%d",&k,&l1,&r1,&l2,&r2);

  init();

  for (int i = 1 ; i <= k ; ++ i) {

    scanf("%s",t+1);

    x = t[1] - 'a' + 1;

    y = t[2] - 'a' + 1;

    x = getfa(x);

    y = getfa(y);

    if (x != y) uni[x] = y;

  }

  for (int i = 0 ; i < 26 ; ++ i)

    (val[0][getfa(i+1)] += gethas(i,l1,r1)) %= MOD;

  for (int i = 0 ; i < 26 ; ++ i)

    (val[1][getfa(i+1)] += gethas(i,l2,r2)) %= MOD;

  int key = 0;

  for (int i = 1 ; i <= 26 ; ++ i)

    key += (val[0][i] != val[1][i]);

  if (!key) return (void) (puts("YES"));

  if (key > 2) return (void) (puts("NO"));

  for (int i = 1 ; i <= 26 ; ++ i) {

    if (val[1][i] != val[0][i]) {

      x = val[1][i] - val[0][i];

      x = (x % MOD + MOD) % MOD;

      if (!mp.count((x))) return (void) (puts("NO"));

      rec[cnt++] = mp[x];

    }

  }

  if (rec[0] == -rec[1]) puts("YES");

  else puts("NO");

}

int main() {

  scanf("%s",s+1);

  n = strlen(s+1);

  for (int i = 0 ; i < 26 ; ++ i) {

    for (int j = 1 ; j <= n ; ++ j)

      has[i][j] = (1ll * has[i][j-1] * BAS + (s[j] == 'a' + i)) % MOD;

  }

  pw[0] = 1;

  for (int i = 1 ; i <= n ; ++ i)

    pw[i] = 1ll * pw[i-1] * BAS % MOD;

  for (int i = 0 ; i <= n ; ++ i)

    mp[pw[i]] = i + 1, mp[MOD - pw[i]] = -i - 1;

  scanf("%d",&m);

  for (int i = 1 ; i <= m ; ++ i)

    solve();

  return 0;

}

小结：解题关键就在于拆分每个字符的贡献，以实现合并。这利用了哈希值容易拆分合并的性质。