题面

大秦为你打开题目传送门

题目描述

两个字符串相似的定义：当且仅当这两个字符串等长且恰好只有一位不同。

例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。

给定N个字符串，判断它们有多少对是相似的。

给定的字符串长度均等于L，且只包含大小写字母、数字、下划线以及 ‘@’ 共64种字符，而且不存在两个相同的字符串。

思路

由于每个字符串的长度相当的小，也就说，我们完全可以枚举那个不一样的位，哈希求最长连号时顺便统计即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const ull P = 131;

int n, L;
char s[30010][210];

ull hsh[30010][210];
ull power[210];
ull t[30010];

void Input() {
    scanf("%d%d", &n, &L);
    for(int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= L; j++) {
            hsh[i][j] = hsh[i][j - 1] * P + s[i][j];
        }
    }
}

void Work() {
    power[0] = 1;
    for(int i = 1; i <= L; i++) {
        power[i] = power[i - 1] * P;
    }
    int ans = 0;
    for(int i = 1; i <= L; i++) {
        for(int j = 1; j <= n; j++) {
            t[j] = hsh[j][L] - (hsh[j][i] - hsh[j][i - 1] * P) * power[L - i] - hsh[j][i - 1] * (power[L - i + 1] - power[L - i]);
        }
        sort(t + 1, t + n + 1);
        int tmp = 1;
        for(int j = 1; j < n; j++) {
            if(t[j] != t[j + 1]) tmp = 1;
            else {
                ans += tmp;
                tmp++;
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    Input();
    Work();
    return 0;
}