CTSC2014/Day1/企鹅QQ

Posted on Apr 28, 2014 By 二价氢

#题目描述

给你若干长度相等的字符串，问编辑距离为1的字符串有多少对

#做法

HASH

我们知道，Hash是会被卡的

桶排+倍增求字典序，把字典序作为Hash的值

这样就不会被卡

但是我还是不会写……

这题能用long long卡过～

或者两重hash也能过

其实Hash是不能被卡掉的！—-VFleaKing Hashkiller III

#AC Code

Data Time Memory Result
1 0.037 s 95055 K Accepted
2 0.040 s 95148 K Accepted
3 0.175 s 96027 K Accepted
4 0.131 s 96027 K Accepted
5 0.464 s 100914 K Accepted
6 0.352 s 100914 K Accepted
7 1.486 s 100914 K Accepted
8 1.943 s 100914 K Accepted
9 1.277 s 100918 K Accepted
10 1.289 s 100914 K Accepted

测试平台：Windows x64 MinGW GCC 4.8.2

编译指令：g++ penguin.cpp -o penguin.exe -static

时间已换算成标准时间

#include <vector>
#include <map>
#include <set>
#include <utility>
using namespace std;
int len=0,n,s,ans,diff;
int hs;
char str[30005][205];
unsigned long long hash[205][2];
pair<unsigned long long,unsigned long long>h[205][30005];
typedef pair<unsigned long long,unsigned long long> puiui;
int chartab[]=
{/*  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F */
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/* 0 */
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/* 1 */
    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,/* 2 */
 /*  0  1  2  3  4  5  6  7  8  9                   */
     1, 2, 3, 4, 5, 6, 7, 8, 9,10,-1,-1,-1,-1,-1,-1,/* 3 */
 /*  @  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O */
    11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,/* 4 */
 /*  P  Q  R  S  T  U  V  W  X  Y  Z              _ */
    27,28,29,30,31,32,33,34,35,36,37,-1,-1,-1,-1,38,/* 5 */
 /*     a  b  c  d  e  f  g  h  i  j  k  l  m  n  o */
    -1,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,/* 6 */
 /*  p  q  r  s  t  u  v  w  x  y  z                */
    54,55,56,57,58,59,60,61,62,63,64,-1,-1,-1,-1,-1,/* 7 */
};
int main()
{
	freopen("penguin.in","r",stdin);
	freopen("penguin.out","w",stdout);
	scanf("%d%d%d",&n,&len,&s);
	if (s==2)
		hs=3;
	else
		hs=67;
	int ans=0,i,j,k,gup;
	for (i=1;i<=n;i++)
	{
		scanf("%s",str[i]+1);
		for (j=1;j<=len;j++)
			hash[j][1]=hash[j-1][1]*hs+chartab[str[i][j]];
		for (j=len;j>=1;j--)
			hash[j][2]=hash[j+1][2]*hs+chartab[str[i][j]];
		for (j=1;j<=len;j++)
			h[j][i]=puiui(hash[j-1][1],hash[j+1][2]);
	}
	for (i=1;i<=len;i++)
		sort(&h[i][1],&h[i][n+1]);
	for (i=1;i<=len;i++)
		for (j=1;j<=n;j++)
		{
			for (k=j+1,gup=1;k<=n;k++)
				if (h[i][j].first==h[i][k].first && h[i][j].second==h[i][k].second)
					gup++;
				else
				{
					j=k-1;
					break;
				}
			ans+=gup*(gup-1)/2;
		}
	printf("%d\n",ans);
	return 0;
}