4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class TheBoringStoreDivOne { public: 4fd800b3a8 2011-02-23 kinaba: // entry point 4fd800b3a8 2011-02-23 kinaba: string J, B; 4fd800b3a8 2011-02-23 kinaba: string find(string J, string B) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: this->J=J; this->B=B; return solve(); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // just for clarifying types 4fd800b3a8 2011-02-23 kinaba: typedef int J_index, B_index; 4fd800b3a8 2011-02-23 kinaba: typedef pair<int,int> J_sub, B_sub; 4fd800b3a8 2011-02-23 kinaba: string jsub(J_index js, J_index je) { return J.substr(js, je-js); } 4fd800b3a8 2011-02-23 kinaba: string bsub(B_index bs, B_index be) { return B.substr(bs, be-bs); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // update if better 4fd800b3a8 2011-02-23 kinaba: void update(string* a, const string& b) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( a->size()<b.size() || (a->size()==b.size() && *a>b) ) 4fd800b3a8 2011-02-23 kinaba: *a = b; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // O(|J|^4) in total 4fd800b3a8 2011-02-23 kinaba: string solve() 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: string result; 4fd800b3a8 2011-02-23 kinaba: for(J_index js=0; js< J.size(); ++js) 4fd800b3a8 2011-02-23 kinaba: for(J_index je=js+1; je<=J.size(); ++je) // for each J[js, je) 4fd800b3a8 2011-02-23 kinaba: for(J_index ks=0; ks< J.size(); ++ks) // try each J[ks, ks+k) which ... 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: // ... is a maximal nonempty prefix of J[js, je) not intersecting with it 4fd800b3a8 2011-02-23 kinaba: int k; 4fd800b3a8 2011-02-23 kinaba: for(k=0; js+k<je && ks+k<J.size() && (ks+k<js || je<=ks); ++k) 4fd800b3a8 2011-02-23 kinaba: if( J[js+k] != J[ks+k] ) 4fd800b3a8 2011-02-23 kinaba: break; 4fd800b3a8 2011-02-23 kinaba: if( k==0 ) 4fd800b3a8 2011-02-23 kinaba: continue; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // we have J[js, js+k)+J[js+k, je) in J, so we want m in B 4fd800b3a8 2011-02-23 kinaba: // J[ks, ks+k) J[js+k,je) + m 4fd800b3a8 2011-02-23 kinaba: string m = findInB(J_sub(js+k,je)); 4fd800b3a8 2011-02-23 kinaba: if( !m.empty() ) 4fd800b3a8 2011-02-23 kinaba: update(&result, jsub(js,je)+m); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return result; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // O(|J|^2 |B|^2) in total 4fd800b3a8 2011-02-23 kinaba: map<J_sub, string> memo_fib; 4fd800b3a8 2011-02-23 kinaba: string findInB(J_sub key) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( memo_fib.count(key) ) 4fd800b3a8 2011-02-23 kinaba: return memo_fib[key]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: string result; 4fd800b3a8 2011-02-23 kinaba: for(string::iterator it=B.begin(); it!=B.end(); ++it) // for each B[ks,ke)==key 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: it = search(it, B.end(), J.begin()+key.first, J.begin()+key.second); 4fd800b3a8 2011-02-23 kinaba: if( it == B.end() ) 4fd800b3a8 2011-02-23 kinaba: break; 4fd800b3a8 2011-02-23 kinaba: B_index ks = it - B.begin(); 4fd800b3a8 2011-02-23 kinaba: B_index ke = ks + (key.second - key.first); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // try all B[ks, ke)+B[ke, kee), and try to find another B[ke, kee) before ks or after kee 4fd800b3a8 2011-02-23 kinaba: for(B_index kee=ke+1; kee<=B.size(); ++kee) 4fd800b3a8 2011-02-23 kinaba: if( canFindBefore(ks, B_sub(ke,kee)) || canFindAfter(kee, B_sub(ke,kee)) ) 4fd800b3a8 2011-02-23 kinaba: update(&result, bsub(ke,kee)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return memo_fib[key] = result; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // O(|B|^4) in total : for each substring m of B, the first and last occurence is memoized 4fd800b3a8 2011-02-23 kinaba: bool canFindBefore(B_index bi, B_sub m) { return firstOccurence(m)+(m.second-m.first) <= bi; } 4fd800b3a8 2011-02-23 kinaba: bool canFindAfter (B_index bi, B_sub m) { return bi <= lastOccurence(m)-(m.second-m.first); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: map<B_sub, B_index> memo_fo; 4fd800b3a8 2011-02-23 kinaba: B_index firstOccurence(B_sub m) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( memo_fo.count(m) ) 4fd800b3a8 2011-02-23 kinaba: return memo_fo[m]; 4fd800b3a8 2011-02-23 kinaba: return memo_fo[m] = search(B.begin(), B.end(), B.begin()+m.first, B.begin()+m.second)-B.begin(); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: map<B_sub, B_index> memo_lo; 4fd800b3a8 2011-02-23 kinaba: B_index lastOccurence(B_sub m) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( memo_lo.count(m) ) 4fd800b3a8 2011-02-23 kinaba: return memo_lo[m]; 4fd800b3a8 2011-02-23 kinaba: int mrs = B.size() - m.second; 4fd800b3a8 2011-02-23 kinaba: int mre = B.size() - m.first; 4fd800b3a8 2011-02-23 kinaba: return memo_lo[m] = B.size() - (search(B.rbegin(), B.rend(), B.rbegin()+mrs, B.rbegin()+mre)-B.rbegin()); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const string& Expected, const string& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (Expected == Received); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, TheBoringStoreDivOne().find(J, B));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string J = "StoreOfJohn"; 4fd800b3a8 2011-02-23 kinaba: string B = "StoreOfBrus"; 4fd800b3a8 2011-02-23 kinaba: string _ = "or"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string J = "JohnAndJohn"; 4fd800b3a8 2011-02-23 kinaba: string B = "John"; 4fd800b3a8 2011-02-23 kinaba: string _ = ""; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string J = "JohnLikesToPlayGames"; 4fd800b3a8 2011-02-23 kinaba: string B = "BrusAlsoLikesToPlayGames"; 4fd800b3a8 2011-02-23 kinaba: string _ = "esToPlayGames"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string J = "abacaba"; 4fd800b3a8 2011-02-23 kinaba: string B = "abacabadabacaba"; 4fd800b3a8 2011-02-23 kinaba: string _ = "abaabacaba"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string J = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 4fd800b3a8 2011-02-23 kinaba: string B = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 4fd800b3a8 2011-02-23 kinaba: string _ = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string J = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 4fd800b3a8 2011-02-23 kinaba: string B = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 4fd800b3a8 2011-02-23 kinaba: string _ = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE