[JSOI]Word Query电子字典

Time Limit:10000MS  Memory Limit:65536K
Total Submit:27 Accepted:11
Case Time Limit:1000MS

Description

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大 量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选 择。
字符串a与字符串b的编辑距离是指：允许对a或b串进行下列“编辑”操作，将a变为b或b变为a，最少“编辑”次数即为距离。
 删除串中某个位置的字母；
 添加一个字母到串中某个位置；
 替换串中某一位置的一个字母为另一个字母；

JSOI团队正在开发一款电子字典，你需要帮助团队实现一个用于模糊查询功能的计数部件：对于一个待查询字符串，如果它是单词，则返回-1；如果 它不是单词，则返回字典中有多少个单词与它的编辑距离为1。

Input

第一行包含两个正整数N (N < = 10,000)和M (M < = 10,000)。
接下来的N行，每行一个字符串，第i + 1行为单词Wi。单词长度在1至20之间。再接下来M行，每行一个字符串，第i + N + 1表示一个待查字符串Qi。待查字符串长度在1至20之间。Wi和Qi均由小写字母构成，文件中不包含多余空格。所有单词互不相同，但是查询字符串可能有 重复。

提示：有50%的数据范围：N < = 1,000，M < = 1,000。

Output

输出应包括M行，第i行为一个整数Xi。Xi = -1表示Qi为字典中的单词；否则Xi表示与Qi编辑距离为1的单词的个数。

Sample Input

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

Sample Output

-1
2
3

Hint

abcd在单词表中出现过；abc与单词abcd、aabc的编辑距离都是1；abcdd与单词abcd、abcde、abced的编辑距离都是1。

Source

JSOI第二轮Contest1
61.187.179.132:8080/JudgeOnline/showproblem
额。这题目告诉我一件事情就是unsigned long long基本是不会冲突的，所以可以放心的用Hash。。直接暴力Hash了，replace的模拟是枚举每一个位置，然后枚举改变成什么，相应的在原串的Hash值+上改变量。效率是(26*Len)，
delete和Insert首先要算出从一个位置到数字首和数字尾的Hash值，然后Delete枚举位置删除就可以了，Insert还要枚举插入那个数。
总共就是(26*Len*m+Len*n)。。。速度虽然慢，还是A掉了(*^__^*)
囧。。为什么别人的程序都是20000KB+的我这个只有500而且还这么慢，悲剧。。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,l,r) for(int i=l;i<=r;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int seed=131,maxl=20+10;
typedef unsigned long long ull;
struct Hash
{
static const int size=17771;
struct node
{
ull key;
int num;
node*next;
node(ull _key,int _num,node*_n):key(_key),num(_num),next(_n){}
}*H[size];
Hash(){memset(H,0,sizeof(H));}
int find(ull code)
{
int h=code%size;
for(node*i=H[h];i;i=i->next)if(i->key==code)return i->num;
return -1;
}
void insert(ull code,int num)
{
//cout<<"I"<<code<<endl;
int h=code%size;
H[h]=new node(code,num,H[h]);
}
}hash;
ull Code(char*s)
{
ull ret=0;
while(*s) ret*=seed,ret+=*(s++);
return ret;
}
int n,m;
void solve()
{
static ull Power[maxl];
char s[maxl];
Power[0]=1;
For(i,1,maxl-1)Power[i]=Power[i-1]*seed;
scanf("%d %d",&n,&m);
rep(i,n) scanf("%sn",s),hash.insert(Code(s),i);
ull Left[maxl],Right[maxl];
while(m–)
{
scanf("%sn",s);ull t=Code(s),x,ret=0,l=strlen(s),tmp;
set<int> S;
if(hash.find(t)!=-1){printf("-1n");continue;}
//Replace a letter
for(int i=0;i<l;i++)
{
for(char c=’a’;c<=’z’;c++)if(c!=s[i])
if((tmp=hash.find(t+Power[l-i-1]*(c-s[i])))!=-1)
S.insert(tmp);
}
//Cal the Left Hash value and the Right Hash value
Left[0]=0;
for(int i=1;i<=l;i++)
Left[i]=Left[i-1]*seed+s[i-1];
Right[l+1]=0;
for(int i=l;i>=1;i–)
Right[i]=Right[i+1]+Power[l-i]*s[i-1];
//Delete a letter
for(int i=1;i<=l;i++)
{
ull x=Left[i-1]*Power[l-i]+Right[i+1];
if((tmp=hash.find(x))!=-1)S.insert(tmp);//cout<<"D"<<endl;
}
//Insert a letter
for(int i=0;i<=l;i++)
{
ull x=Left[i]*Power[l-i+1]+Right[i+1];
for(char c=’a’;c<=’z’;c++)if((tmp=hash.find(x+Power[l-i]*c))!=-1)S.insert(tmp);//cout<<"I"<<endl;
}
printf("%dn",S.size());
}
}
int main()
{
//freopen("in","r",stdin);
solve();
}