CTSC2014 企鹅QQ

wjh15101051's space

卧薪尝胆，厚积薄发。

CTSC2014 企鹅QQ

Date: Sat Sep 22 15:10:41 CST 2018

In Category: NoCategory

Description：

给你 $n$ 个两两不同字符串，每个长度都为 $l$ ，问有多少对字符串只有一位不同。

$1\leqslant n \leqslant 30000,1\leqslant l \leqslant 200$

Solution：

$\text{hash}$ 一个前缀一个后缀枚举每一位统计即可，统计的时候可以把所有哈希值拿出来排序，因为 $\text{map}$ 太慢了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

typedef long long ll;

int n,l,m;

#define MAXN 30010

#define MAXL 210

#define BASE1 19260817

#define BASE2 997

#define MOD1 998244353 

#define MOD2 1000000007

char c[MAXN][MAXL];

typedef long long ll;

int pre1[MAXN][MAXL],suf1[MAXN][MAXL],pre2[MAXN][MAXL],suf2[MAXN][MAXL];

#define fi first

#define se second

pair< pair<int,int>,pair<int,int> > s[MAXN];

int tot[MAXN];

int main()

{

	scanf("%d%d%d",&n,&l,&m);

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

	{

		scanf("%s",c[i] + 1);

		for(int k = 1;k <= l;++k)pre1[i][k] = ((ll)pre1[i][k - 1] * BASE1 + c[i][k]) % MOD1;

		for(int k = 1;k <= l;++k)pre2[i][k] = ((ll)pre2[i][k - 1] * BASE2 + c[i][k]) % MOD2;

		for(int k = l;k >= 1;--k)suf1[i][k] = ((ll)suf1[i][k + 1] * BASE1 + c[i][k]) % MOD1;

		for(int k = l;k >= 1;--k)suf2[i][k] = ((ll)suf2[i][k + 1] * BASE2 + c[i][k]) % MOD2;

	}

	long long ans = 0;

	for(int p = 1;p <= l;++p)

	{

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

		{

			s[i] = make_pair(make_pair(pre1[i][p - 1],pre2[i][p - 1]),make_pair(suf1[i][p + 1],suf2[i][p + 1]));

			tot[i] = 1;

		}

		sort(s + 1,s + 1 + n);

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

		{

			if(s[i] == s[i - 1])

			{

				tot[i] += tot[i - 1];

				ans += tot[i - 1];

			}

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 字符串-hash

wjh15101051