Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
结果暴力能过,还以为KMP呢。用STL + cin 结果79MS。汗。。。贴下code。#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; #define NotFound 4294967295 bool comp(const string& a, const string& b) { if (a.length() != b.length()) return a.length() > b.length(); else return a < b; } int main() { int nCase, mSeq; vector <string> mStr; vector <string> ansStr; cin >> nCase; while ( nCase-- ) { cin >> mSeq; for (int i = 0; i < mSeq; i++) { string tmp; cin >> tmp; mStr.push_back(tmp); } for (int i = 0; i < (int)mStr[0].length(); i++) //enum all subsequence of the first string and its length not less than three for (int j = 3; i+j <= (int) mStr[0].length(); j++) { string tmp = mStr[0].substr(i, j); int flag = 1; for (int k = 1; k < mSeq; k++) { if (mStr[k].find(tmp) == NotFound) { flag = 0; break; } } if (flag == 1) ansStr.push_back(tmp); } if ( !ansStr.empty() ) { sort(ansStr.begin(), ansStr.end(), comp); cout << ansStr[0] << endl; } else cout << "no significant commonalities" << endl; ansStr.clear(); mStr.clear(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator