Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

结果暴力能过,还以为KMP呢。用STL + cin 结果79MS。汗。。。贴下code。

Posted by CodeChomper at 2010-08-13 15:46:56 on Problem 3080 and last updated at 2010-08-13 15:48:55
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator