P4503 [CTSC2014] 企鹅 QQ 解题报告

Desciptoin
小 Q 是 PenguinQQ 网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如 Penguin1，Penguin2，Penguin3……于是小 Q 决定先对这种相似的情形进行统计。

小 Q 定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。而小 Q 想知道，在给定的 $n$ 个账户名称中，有多少对是相似的。

为了简化你的工作，小Q给你的 $N$ 个字符串长度均等于 $L$ ，且只包含大小写字母、数字、下划线以及‘@’共64种字符，而且不存在两个相同的账户名称。

Solution
字符串 hash 的简单应用。

每次枚举一位，然后计算删除这一位后的hash值，放到数组里排序统计即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x * f;
}
const int N = 30005, L = 205, base = 233;
int n, l, S, ans;
char s[N];
ull pw[L], hs[N][L], H[N];
signed main () {
    n = read(); l = read(); S = read();
    pw[0] = 1; for (int i = 1; i <= l; ++ i) pw[i] = pw[i-1] * base;
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= l; ++ j) hs[i][j] = hs[i][j-1] * base + s[j];
    }
    for (int k = 1; k <= l; ++ k) {
        for (int i = 1; i <= n; ++ i) H[i] = hs[i][l] - hs[i][k] * pw[l-k] + hs[i][k-1] * pw[l-k];
        sort(H + 1, H + 1 + n); int t = 1;
        for (int i = 1; i <= n; ++ i) 
            if (H[i] == H[i-1]) ans += t, ++ t;
            else t = 1; 
    }
    printf("%lld\n", ans);
    return 0;
}