#include iostream #include vector #include string #include cstring #include set using namespace std; class lengthLess { public: bool operator()(const string str1, const string str2) { if (str1.length() == str2.length()) { return str1 str2;
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
using namespace std;
class lengthLess {
public:
bool operator()(const string & str1, const string & str2) {
if (str1.length() == str2.length()) {
return str1 < str2;
} else {
return str1.length() > str2.length();
}
}
};
const int GENE_LENGTH = 60;
void getLCS(int strNum, const vector<string> &strArray) {
string baseStr = strArray.front();
set<string, lengthLess> subStringSet;
bool found = false;
for (int begin = 0; begin <= 56; begin++) {
for (int end = begin + 2; end < GENE_LENGTH; end++) {
subStringSet.insert(baseStr.substr(begin, end - begin + 1));
}
}
set<string, lengthLess>::iterator setIt = subStringSet.begin();
for ( ; setIt != subStringSet.end(); setIt++) {
bool match = true;
vector<string>::const_iterator it = strArray.begin();
for (it += 1; it!= strArray.end(); it++) {
if (!strstr((*it).c_str(), (*setIt).c_str())) {
match = false;
break;
}
}
if (match) {
cout<<*setIt<<endl;
found = true;
break;
}
}
if (!found) {
cout<<"no significant commonalities"<<endl;
}
}
int main() {
int caseNum = 0;
cin>>caseNum;
for (int i = 0; i < caseNum; i++) {
int strNum = 0;
cin>>strNum;
vector<string> strArray;
for (int j = 0; j< strNum; j++) {
string input = "";
cin>>input;
strArray.push_back(input);
}
getLCS(strNum ,strArray);
}
}C++ 63ms AC.
没啥讲的， 暴力搜索过的.......， 并且这还是用了STL, 不用STL估计更快， 就是麻烦点.
直接穷举第一个字符串的所有>=3的子串， 预先保存在set里(去重加重新按照长度和字母顺序排列)。
然后遍历字串的set， 与剩下的所有gene字符串进行strstr匹配（速度快些）, 一旦有一个完全匹配了， 就是最终答案(因为set已经将子串排列过了， 第一个匹配的
一定是最长且字母顺序最靠前的), 如果全部完了还没有，那么就no common.
一开始还想着LCS搞起，不过貌似更麻烦， 看样子确实在一定的规模内， 有时候穷举反而最简单粗暴有效.
就当练习了一遍STL使用和穷举吧.
对了, STL的 stack queue之类的容器没有iterator, 因为跟他们的语义不符. 以前没注意过。