简答题
偏难
#7300
拼写检查 现在有一些英语单词需要做拼写检查, 你的工具是一本词典。 需要检查的单词, 有的是词典中的单词, 有的与词典中的单词相似, 你的任务是发现这两种情况。…
拼写检查
现在有一些英语单词需要做拼写检查, 你的工具是一本词典。 需要检查的单词, 有的是词典中的单词, 有的与词典中的单词相似, 你的任务是发现这两种情况。 单词 A 与单词 B 相似的情况有三种:
1、 删除单词 A 的一个字母后得到单词 B;
2、 用任意一个字母替换单词 A 的一个字母后得到单词 B;
3、 在单词 A 的任意位置增加一个字母后得到单词 B。
你的任务是发现词典中与给定单词相同或相似的单词。
时间限制: 2000
内存限制: 65536
输入
第一部分是词典中的单词, 从第一行开始每行一个单词, 以"#"结束。
词典中的单词保证不重复, 最多有 10000 个。 第二部分是需要查询的单词, 每行一个, 以"#"结束。 最多有 50 个需要查询的单词。 词典中的单词和需要查询的单词均由小写字母组成, 最多包含 15 个字符。
输出
按照输入的顺序, 为每个需要检查的单词输出一行。 如果需要检查的单词出现在词典中, 输出“?x is correct", ?x 代表需要检查的单词。
如果需要检查的单词没有出现在词典中, 则输出"?x: ?x1 ?x2 ...?xn",其中?x 代表需要检查的单词, ?x1...?xn 代表词典中与需要检查的单词相似的单词, 这些单词中间以空格隔开。 如果没有相似的单词, 输出"?x:"即可。
样例输入
i is has have be my more contest me too if award # me aware m contest hav oo or i fi mre #
样例输出
me is correct aware: award m: i my me contest is correct hav: has have oo: too or: i is correct fi: i mre: more me
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
bool IsSame(string a, string b) {
char drop;
// a短
int mi = min(a.length(), b.length());
string a1 = a;
string b1 = b;
sort(a1.begin(), a1.end());
sort(b1.begin(), b1.end());
bool exis = false;
for (int i = 0; i < mi; i++) {
if (a1[i] != b1[i]) {
drop = b1[i];
exis = true;
break;
}
}
if (!exis) {
drop = b1[b1.length() - 1];
}
string ti;
bool ex = false;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i]) {
ex = true;
ti = a.substr(0, i);
ti = ti + drop;
ti = ti + a.substr(i, 1000);
break;
}
}
if (!ex) {
ti = a + drop;
}
if (ti != b) {
return false;
} else {
return true;
}
}
int main() {
string dictionary[10010];
string words[60];
string a, b;
int dic = 0;
int m = 0;
while (1) {
cin >> a;
if (a == "#") {
break;
} else {
dictionary[dic++] = a;
}
}
while (1) {
cin >> b;
if (b == "#") {
break;
} else {
words[m++] = b;
}
}
for (int i = 0; i < m; i++) {
bool you = false;
for (int j = 0; j < dic; j++) {
if (dictionary[j] == words[i]) {
cout << words[i] << " is correct" << endl;
you = true;
break;
}
} // 判断是否完全相同。
if (you != true) {
cout << words[i] << ": ";
for (int j = 0; j < dic; j++) {
int somewhat = words[i].length() - dictionary[j].length();
if (somewhat == 0) {
for (int k = 0; k < words[i].length(); k++) {
if (words[i][k] != dictionary[j][k]) {
string tishen = words[i];
tishen[k] = dictionary[j][k];
if (tishen == dictionary[j]) {
cout << dictionary[j] << " ";
}
}
}
}
if (abs(somewhat) == 1) {
if (words[i].length() > dictionary[j].length()) {
if (IsSame(dictionary[j], words[i])) {
cout << dictionary[j] << " ";
}
} else {
if (IsSame(words[i], dictionary[j])) {
cout << dictionary[j] << " ";
}
}
}
}
cout << endl;
}
}
system("pause");
}</pre>
这道题暂未补解析。