| ||||||||||
| 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