题解：AT_abc483_e [ABC483E] Typo Pairs

· · 题解

这篇文章中，题中的字母都变成了小写字母。

算法

本题需要求出有多少个 1\le i<j\le n 使得 s_i 和 s_j 的汉明距离不超过 2。

对于汉明距离小于等于 2，首先考虑，对于 1\le k<l\le m，有多少个 1\le i<j\le n 使得 s_i 和 s_j 的第 x\ (x\ne k,l) 位字符相等，这时可以对于字符串，忽略第 k,l 位，剩余的 m-2 个字符，可以进行哈希，由于范围不超过 26^{m-2}\le 26^4=456976，可以使用多项式哈希，用数组存储，并且不会冲突。遍历这 n 个字符串组成的序列，对于每一个字符串，计算它的哈希 h，然后可以查询，之前有多少个字符串，哈希也是 h，然后加到答案。

这里面将汉明距离小于等于 1 的情况重复了，所以需要减去，对于索引 k 之外的字符部分需要相同，那么依然需要计算哈希，范围不超过 26^{m-1}\le 26^5=11881376，依然可以使用数组存下。然后也是相同的遍历方法，对于遍历每一个字符串时，计算哈希 h，查询到之前的哈希为 h 的字符串个数 c 之后，需要将答案减去 (m-2)c，因为上一段中，包含 k 的计数有 m-1 次。

这个时候，汉明距离等于 0 的字符串对数 c，也需要修正，具体的，需要对答案加上 (m-2)(m-1)c/2，因为第一次共计了 m(m-1)/2 次，第二次又减去了 m(m-2) 次，所以需要加上 K 个 c，使得

m(m-1)/2-m(m-2)+K=1

成立，解得 K=(m-2)(m-1)/2，这就说明需要对答案加上 (m-2)(m-1)c/2，就能使得最终计算结果正确。

时间复杂度是 \mathcal{O}\left(nm^3+nm\log n\right) 或 \mathcal{O}\left(nm^3+{\lvert\Sigma\rvert}^{m-2}m^2+{\lvert\Sigma\rvert}^{m-1}m+nm\log n\right)（取决于清空数组的方式），空间复杂度是 \mathcal{O}\left(nm+{\lvert\Sigma\rvert}^{m-1}\right)，其中 \Sigma 是字符集，这里就是 26 个小写字母组成的集合。

代码

下面是时间复杂度是 \mathcal{O}\left(nm^3+{\lvert\Sigma\rvert}^{m-2}m^2+{\lvert\Sigma\rvert}^{m-1}m+nm\log n\right) 的实现。（链接）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, m, num[26*26*26*26*26], tmp=1;
char s[(int)2e5][7];
long long ans, c;
int cmp(const void *a, const void *b) {return memcmp(a, b, m);}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;++i) scanf("%s", s[i]);
    for(int k=0;k<m;++k) for(int l=k+1;l<m;++l) {
        memset(num, 0, 26*26*26*26*sizeof(int));
        for(int i=0;i<n;++i){
            int h = 0;
            for(int j=0;j<m;++j) if (j!=k && j!=l) h = h * 26 + s[i][j] - 'a';
            ans += num[h];
            ++num[h];
        }
    }
    for(int k=0;k<m;++k) {
        memset(num, 0, sizeof(num));
        for (int i=0;i<n;++i) {
            int h=0;
            for (int j=0;j<m;++j) if (j!=k) h=h*26+s[i][j]-'a';
            ans -= (long long)(num[h]) * (m-2);
            ++num[h];
        }
    }
    qsort(s, n, 7, cmp);
    for(int i=1;i<n;++i){
        if (memcmp(s[i],s[i-1],m)) c += (long long)tmp*(tmp-1)/2, tmp=1;
        else ++tmp;
    }
    if (tmp) c += (long long)tmp*(tmp-1)/2;
    ans += c * (m-1) * (m-2) / 2;
    printf("%lld\n", ans);
}

下面是时间复杂度是 \mathcal{O}\left(nm^3+nm\log n\right) 的实现。（链接）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, m, num[26*26*26*26*26], tmp=1;
int op[(int)2e5], ops;
char s[(int)2e5][7];
long long ans, c;
int cmp(const void *a, const void *b) {return memcmp(a, b, m);}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0;i<n;++i) scanf("%s", s[i]);
    for(int k=0;k<m;++k) for(int l=k+1;l<m;++l) {
        while (ops) --num[op[--ops]];
        for(int i=0;i<n;++i){
            int h = 0;
            for(int j=0;j<m;++j) if (j!=k && j!=l) h = h * 26 + s[i][j] - 'a';
            ans += num[h];
            ++num[h];
            op[ops] = h;
            ++ops;
        }
    }
    for(int k=0;k<m;++k) {
        while (ops) --num[op[--ops]];
        for (int i=0;i<n;++i) {
            int h=0;
            for (int j=0;j<m;++j) if (j!=k) h=h*26+s[i][j]-'a';
            ans -= (long long)(num[h]) * (m-2);
            ++num[h];
            op[ops] = h;
            ++ops;
        }
    }
    qsort(s, n, 7, cmp);
    for(int i=1;i<n;++i){
        if (memcmp(s[i],s[i-1],m)) c += (long long)tmp*(tmp-1)/2, tmp=1;
        else ++tmp;
    }
    if (tmp) c += (long long)tmp*(tmp-1)/2;
    ans += c * (m-1) * (m-2) / 2;
    printf("%lld\n", ans);
}