A . 单词拼写检查(无错哈希)

简介: A . 单词拼写检查(无错哈希)

1.描述:


叶妍霜有一个宠物机器人,它可以检查主人输入的单词是否有拼写错误。这是因为宠物机器人内置有一单词库,里面存有常用的单词。待主人输入一个单词后,它就到库中查找是否有这种拼写,以判断正误。

现给定一个单词库,库中存入10 000个以下的单词(单词长度3~20),且单词没有按任何顺序排列,另给定10 000个以下的待查单词,要求编程输出这些待查单词中有多少个词拼写错误。题中单词均由小写字母组成。


2. 输入:


第一行为一个数字N,表示单词库里有N个单词,随后是N行单词。紧接着一个数M,表示待查单词数,随后是M行待查单词。


3.输出:


输出拼写错误的单词数。


4.样例输入:


5
apple
be
love
up
down
3
up
down
bee


5.样例输出:


1


6.题目大意:


给出单词库,其中有n个单词,给出m次询问,查询给出的单词是否在单词库存在(存在就是写对了,不存在就是写错了)


7.思路


哈希入门题,练练无错哈希


无错哈希,就是遇到冲突后往后找到一个一个没用过的键值,来储存数据


8.代码


#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e5+100;
const int p = 1073741824;
const double eps = 1e-8;
string a[N+1],s;
int n,m;
int cnt;
//每个字符串给出对应的哈希值
int hashh(string s)
{
  int len=s.size();
  int k=s[0]*10000+s[(len-1)/2]*100+s[len-1]*10;
  return (k+N)%N;
}
//插入
void insert(string s)
{
  int key=hashh(s);
  while(a[key]!="")//找到一个没有用过的key
  {
    if(a[key]==s) return ;//找到相同单词,跳出就行了
    key++;
    if(key==N+1) key=1;//到达边界更换key
  }
  a[key]=s;//找到一个没用过的位置插进去
}
//查找
void find(string s)
{
  int key=hashh(s);
  while(a[key]!="")
  {
    if(a[key]==s) return ;//找到就是没写错
    else
    {
      key++;
      if(key==N+1) key=1;
    }
  }
  cnt++;//每找到这个单词但是出现了没用过的key值,说明这个单词不存在
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>s;
    insert(s);
  }
  cin>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>s;
    find(s);
  }
  cout<<cnt;
  return 0;
}

目录
相关文章
|
开发框架 安全 前端开发
[ 代码审计篇 ] Java web 代码审计 详解(一)
之前写了一篇关于代码审计流程的文章,有小伙伴私聊我说不太好理解,这里开始介绍 Java web 的代码审计,同样的来捋一捋审计思路,这就相对要具体一些。
2307 0
[ 代码审计篇 ] Java web 代码审计 详解(一)
|
7月前
|
人工智能 自然语言处理 搜索推荐
现在最火的AI是怎么应用到体育行业的
AI在体育行业的应用日益广泛,涵盖数据分析、伤病预防、观众体验、裁判辅助等多个领域。通过传感器和可穿戴设备,AI分析运动员表现,提供个性化训练建议;预测伤病风险,制定康复方案;优化比赛预测和博彩指数;提升观众的个性化内容推荐和沉浸式观赛体验;辅助裁判判罚,提高准确性;发掘青训人才,优化训练计划;智能管理场馆运营和票务;自动生成媒体内容,提供实时翻译;支持电竞分析和虚拟体育赛事;并为运动员提供个性化营养和健康管理方案。未来,随着技术进步,AI的应用将更加深入和多样化。
|
Python
用python实现背单词的功能(python3经典编程案例)
这篇文章介绍了如何使用Python和Tkinter库实现一个背单词的桌面应用,通过读取文本文件中的单词列表,并在GUI界面中随机显示单词及其音标和解释。
245 10
|
存储 关系型数据库 MySQL
DataX:导入4字节UTF8编码(生僻字)到Mysql数据库的utf8mb4数据表
MySql数据库的编码支持UFT8字符集。utf-8编码可能是2个字节、3个字节、4个字节的字符,MYSQL的utf-8编码,只支持3个字节的字符。汉字中很多生僻字都是4个字节的字符,日常生活中人的姓名就会有很多高位的生僻字。
6513 1
|
Web App开发 JavaScript 前端开发
Node.js 常用命令
Node.js 常用命令
124 0
|
小程序 Python
python背单词小程序
python背单词小程序
140 1
|
关系型数据库 MySQL 开发工具
docker 启动一个mysql服务
docker 启动一个mysql服务
522 0
|
机器学习/深度学习 算法 数据可视化
斯坦福tensorflow教程(三) 线性和逻辑回归
斯坦福tensorflow教程(三) 线性和逻辑回归
200 0
斯坦福tensorflow教程(三) 线性和逻辑回归
|
前端开发 JavaScript
|
自然语言处理 C#
WPF 4 单词拼写检查(SpellCheck)
原文:WPF 4 单词拼写检查(SpellCheck)      在WPF中 Textbox 和RichTextBox 控件都内置了拼写检查属性,但该属性目前默认仅支持English、Spanish、French 和German 四种语言。
1024 0