[CTSC2014] 企鹅 QQ

链接

题意就是找出有多少字符串相似(两个字符串对应每个位置之后只有一处不同)

我们可以枚举每一个字符串单独去掉某个字符后的hash值(最好双哈希)

但要注意去掉的位置,因此我们需要将每个位置单独进行处理

一开始我使用unordered_map来存储hash,但是超时了

查阅资料发现unordered_map在面对大数据(这题达到30000)时,会显得有点鸡肋,因此选择用二维数组存储

一个小细节:计算右半部分的hash,减法可能造成负数结果,需要补上mod

代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;
const int base = 2333;
using namespace std;

void solve() {
	int t, n, k;
	cin >> t >> n >> k;
	vector<ll>h1(n + 1, 0), h2(n + 1, 0), b1(n + 1, 1), b2(n + 1, 1);
	vector<vector<ll>>keys(n, vector<ll>(t));
	for (int i = 1;i <= n;i++) {
		b1[i] = b1[i - 1] * base % mod1;
		b2[i] = b2[i - 1] * base % mod2;
	}
	for (int m = 0;m < t;m++) {
		string str;
		cin >> str;
		
		for (int i = 1;i <= n;i++) {
			h1[i] = h1[i - 1] * base % mod1;
			h2[i] = h2[i - 1] * base % mod2;
			if (k == 64) {
				int val = str[i - 1];
				if ('0' <= val && val <= '9') h1[i] += val - '0', h2[i] += val - '0';
				else if ('a' <= val && val <= 'z') h1[i] += val - 'a' + 10, h2[i] += val - 'a' + 10;
				else if ('A' <= val && val <= 'Z') h1[i] += val - 'A' + 36, h2[i] += val - 'A' + 36;
				else if (val == '_') h1[i] += 62, h2[i] += 62;
				else h1[i] += 63, h2[i] += 63;
			}
			else {
				h1[i] += str[i - 1] - '0';
				h2[i] += str[i - 1] - '0';
			}
			h1[i] %= mod1;
			h2[i] %= mod2;
		}
		for (int i = 1;i <= n;i++) {			
			ll hash1 = (h1[n] - h1[i] * b1[n - i] % mod1 + mod1) % mod1 + (h1[i - 1] * b1[n - i]) % mod1;
			ll hash2 = (h2[n] - h2[i] * b2[n - i] % mod2 + mod2) % mod2 + (h2[i - 1] * b2[n - i]) % mod2;
			hash1 %= mod1, hash2 %= mod2;
			ll hash = hash1 * mod1 + hash2;
			keys[i-1][m] = hash;
		}
	}
	ll ans = 0;
	for (int i = 0;i < n;i++) {
		sort(keys[i].begin(), keys[i].end());
		ll cnt = 1;
		for (int j = 0;j < t - 1;j++) {
			if (keys[i][j] == keys[i][j + 1]) cnt++;
			else {
				ans += (cnt * (cnt - 1) / 2);
				cnt = 1;
			}
		}
		ans += (cnt * (cnt - 1) / 2);
	}
	cout << ans;
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

时间复杂度:O(n * t)

空间复杂度:O(n * t)