poj-1035如何通过长尾关键词优化搜索排名？

本文共计967个文字，预计阅读时间需要4分钟。

伪创新可以简化改写为：

假创新

#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字符串就可以了.

这道题，　暴力搜也能过，　毕竟暴搜不需要复杂的数据结构，也不需要考虑排序的问题，　很有可能最后是最快的.