#include set #include string #include iostream #include vector using namespace std; class intLess { public: bool operator() (const int int1, const int int2) const { return int1 int2; } }; const char MAX_LENGTH = 15; setint, intLess dict[MAX
#include <set>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
class intLess {
public:
bool operator() (const int int1, const int int2) const {
return int1 < int2;
}
};
const char MAX_LENGTH = 15;
set<int, intLess> dict[MAX_LENGTH];
vector<string> originalDict;
int compareWithString(const string & str1, const string & str2) {
if (str1.length() == str2.length()) {
int noMatchNum = 0;
for (int i = 0; i < str1.length() ; i++) {
if (str1[i] != str2[i]) {
if (++noMatchNum >= 2) {
return 2;
}
}
}
return noMatchNum;
} else if (str1.length() + str2.length() == 1) {
return 1;
} else {
int length1 = str1.length();
int length2 = str2.length();
const string & longer = length1 > length2 ? str1 : str2;
const string & shorter = length1 <= length2 ? str1 : str2;
int minLength = shorter.length();
int noMatchPos = -1;
int i;
for (i = 0; i < minLength ; i++) {
if (str1[i] != str2[i]) {
noMatchPos = i;
break;
}
}
if (i == minLength && -1 == noMatchPos) {
return 1;
} else {
if (longer.substr(noMatchPos+1) == shorter.substr(noMatchPos)) {
return 1;
} else {
return 2;
}
}
}
}
void printCandidate(const string & checkStr, const set<int, intLess> & resultSet) {
set<int, intLess>::const_iterator itRes = resultSet.begin();
cout<<checkStr<<":";
for (;itRes != resultSet.end(); itRes++) {
cout<<" "<<originalDict[*itRes];
}
cout<<endl;
}
int checkWithSet(const string & checkStr, const set<int, intLess> & dictSet, set<int, intLess> & resultSet) {
set<int, intLess>::const_iterator it = dictSet.begin();
for( ;it != dictSet.end(); it++) {
if (!compareWithString(checkStr, originalDict[*it])) {
cout<<checkStr<<" is correct"<<endl;
return 1;
} else if (1 == compareWithString(checkStr, originalDict[*it])) {
resultSet.insert(*it);
}
}
return 2;
}
#define RETURN_IF1(res) do { if (1 == res) { return;} } while(0)
void checkWithDict (const string& checkStr) {
int length = checkStr.size();
set<int, intLess> resultSet;
if (length == 1) { // only compare with 1, 2
RETURN_IF1(checkWithSet(checkStr, dict[0], resultSet));
checkWithSet(checkStr, dict[1], resultSet);
} else if (length == MAX_LENGTH) { // only compare with MAX_LENGTH MAX_LENGTH-1
RETURN_IF1(checkWithSet(checkStr, dict[MAX_LENGTH-1], resultSet));
checkWithSet(checkStr, dict[MAX_LENGTH-1-1], resultSet);
} else { // compare with length +0, +1, -1
RETURN_IF1(checkWithSet(checkStr, dict[length-1], resultSet));
checkWithSet(checkStr, dict[length-1-1], resultSet);
checkWithSet(checkStr, dict[length+1-1], resultSet);
}
printCandidate(checkStr, resultSet);
}
int main() {
while(1) {
string input = "";
cin>>input;
if (input == "#") {
break;
} else {
originalDict.push_back(input);
dict[input.length()-1].insert(originalDict.size()-1);
}
}
while(1) {
string check = "";
cin>>check;
if (check == "#") {
break;
} else {
checkWithDict(check);
}
}
}C++ AC, 688ms, g++直接TLE...... 开源和商业效率差的这么多
时间也在预料内，毕竟用了STL，效率换易用，c++编译器还挺严格，在我取const 的set的iterator时， 要求用const_iterator, 微软还是挺严谨的.
一开始没想着这道题对性能还有要求， 看还有人暴力搞过的(不过也有可能，STL对性能的影响还是很大的)，
因为最后输出的时候要求按照输入的顺序进行输出， 因此就搞了套数据结构:
一个vector顺序的保存输入数组， 同时一个set（现在看，根本没必要， 排序又不在这里做，把他换成vector, 时间估计更少）数组则保存每个长度的
输入字符串， set[0]保存的就是长度是１的字符串在vector中的序号（避免了数据冗余，很多符合数据结构，对真正的数组只保存一份， 一般保存的都是引用），
以此类推， 这样做的好处是， 在比较的时候就省力了， 按照题意， 一个字符串最多和自己长度相等已经+/-1的字符串能够匹配， 因此如果一个字符串长度是l,
那么可能匹配他的就只有长度位l-1, l , l+1的字典字符串（l==１和l==MAX_length特殊考虑），至于匹配， 用的是最笨的办法, 没啥说的.
最后要先比较同等长度的， 因为同等长度有可能由完全匹配，那么直接打印完全匹配的即可， 如果没有，那么就放在一个临时的set里面，set按照序号排序，最后
输出的时候，用序号取到vector字符串就可以了.
这道题， 暴力搜也能过， 毕竟暴搜不需要复杂的数据结构，也不需要考虑排序的问题， 很有可能最后是最快的.