POJ 1035 Spell checker(串)
2024-08-30 01:20:06
题目网址:http://poj.org/problem?id=1035
思路:
看到题目第一反应是用LCS ——最长公共子序列 来求解。因为给的字典比较多,最多有1w个,而LCS的算法时间复杂度是O(n*m),n,m分别对应两个字符串的长度。还要乘上字典的个数和所要匹配的单词数,不出意外地。。超时了。
后面就想到了暴力求解,直接枚举所有情况,先判断字符串长度差是否大于1,大于1的话直接进行下一个循环,否则再继续划分。(len对应字典词长度,l对应要查询的词长度)
假设匹配成功,只会有以下三种情况。
1. len==l ,只可能是完美匹配,或是替换一个字母
2. len-1==l,查询的词要添加一个字母
3. len==l-1,查询的词要删去一个字母
代码:
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
char word[][];
char str[];
int main(){
int cnt=-;
while (gets(word[++cnt])!=NULL && word[cnt][]!='#');
while (gets(str)!=NULL && str[]!='#') {
vector<int>v;
int ok=;
int l=(int)strlen(str);
printf("%s",str);
for (int i=; i<cnt; i++) {
int len=(int)strlen(word[i]);
int cur=,j=,k=;
if(fabs(len-l)>) continue;
if(len-l==){//情况1
while (str[j] && word[i][j] && cur<=) {
if (str[j]!=word[i][j]) cur++;
j++;
}
if(cur==){
ok=;
printf(" is correct\n");
break;
}
}else if(len-l==){//情况2
while (str[k] && word[i][j]) {
if(str[k]!=word[i][j]){
cur++,j++;
continue;
}
j++;k++;
}
}else if(l-len==){//情况3
while (str[k] && word[i][j]) {
if(str[k]!=word[i][j]){
cur++,k++;
continue;
}
j++;k++;
}
}
if(cur<=) v.push_back(i); }
if(!ok){
printf(":");
for (int j=; j<v.size(); j++) {
printf(" ");
printf("%s",word[v[j]]);
}
printf("\n");
}
}
return ;
}
另附上用LCS做的超时版本。。有用LCS过的 欢迎讨论
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
char word[][];
char str[];
int main(){
int cnt=-;
while (gets(word[++cnt])!=NULL && word[cnt][]!='#');
while (gets(str)!=NULL && str[]!='#') {
vector<int>v;
int ok=;
int l=(int)strlen(str);
printf("%s",str);
for (int i=; i<cnt; i++) {
int lcs[][];
int Max=;
int len=(int)strlen(word[i]);
if(fabs(len-l)>) continue;
memset(lcs, , sizeof(lcs));
for (int j=; j<len; j++) {
for (int k=; k<l; k++) {
if(word[i][j]==str[k]) lcs[j+][k+]=lcs[j][k]+;
else lcs[j+][k+]=max(lcs[j+][k], lcs[j][k+]);
Max=max(Max, lcs[j+][k+]);
}
}
if(max(len,l)==Max){//完全匹配
ok=;
printf(" is correct\n");
break;
}else if(max(len,l)==Max+){//增删改其中的一个情况
if(len==Max || l==Max){//增删情况
v.push_back(i);
}else{
int j=;
int cur=;
while (word[i][j] && str[j]) {
if(word[i][j]==str[j]) cur++;
j++;
}
if(cur==Max){//修改一个的情况
v.push_back(i);
}
}
}
}
if(!ok){
printf(":");
for (int j=; j<v.size(); j++) {
printf(" ");
printf("%s",word[v[j]]);
}
printf("\n");
}
}
return ;
}
最新文章
- bzoj4196
- Python:常见操作字符串的函数
- jquery之clone()方法详解
- Ubuntu装机必备
- Spark与Hadoop计算模型的比较分析
- IDE开发<;LER-Studio>;(1)::UI设计
- 使用python解数独
- 关于shiro权限管理的一些总结
- 为Tornado框架加上基于Redis或Memcached的session 【第三方】
- Android初级教程理论知识(第二章布局&;读写文件)
- 蓝桥杯 历届试题 幸运数 dfs
- win10 开启蓝 由于其配置信息(注册表中的)不完整或已损坏
- Gitlab注册时报错:There was an error with the reCAPTCHA. Please solve the reCAPTCHA again.
- Python基础之Python分类
- [转载]windows下安装Python虚拟环境virtualenv,virtualenvwrapper-win
- Scala之隐式转换implicit详解
- jQuery.ajax发送image请求格式
- cron执行service
- 用js或css实现淡入淡出
- LeetCode--198--打家劫舍
热门文章
- ansible-playbook流程控制-loops循环使用
- 启动第二个activity,然后返回数据给第一个数据
- SSM框架中测试单元的使用,spring整合Junit
- 23种设计模式之模板方法(Template Pattern)
- 阿里云服务器CentOS6.9防火墙启动无效--iptables消失
- shiro使用注解(@RequiresPermissions等)不无效及异常处理
- windows 安装gitbook并使用gitbook editor可视化工具
- 一台机器上搭建多个redis实例的配置文件修改部分
- maven私服 nexus 的安装与使用
- 记录一次redis cpu异常升高的排插思路