Artifact Content
Not logged in

Artifact 4377d1219d057c6f99bfee8d063469055259e9ff


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class TheBoringStoreDivOne { public:
	// entry point
	string J, B;
	string find(string J, string B) 
	{
		this->J=J; this->B=B; return solve();
	}

	// just for clarifying types
	typedef int           J_index, B_index;
	typedef pair<int,int> J_sub,   B_sub;
	string jsub(J_index js, J_index je) { return J.substr(js, je-js); }
	string bsub(B_index bs, B_index be) { return B.substr(bs, be-bs); }

	// update if better
	void update(string* a, const string& b)
	{
		if( a->size()<b.size() || (a->size()==b.size() && *a>b) )
			*a = b;
	}

	// O(|J|^4) in total
	string solve()
	{
		string result;
		for(J_index js=0;    js< J.size(); ++js)
		for(J_index je=js+1; je<=J.size(); ++je) // for each J[js, je)
		for(J_index ks=0;    ks< J.size(); ++ks) // try each J[ks, ks+k) which ...
		{
			// ... is a maximal nonempty prefix of J[js, je) not intersecting with it
			int k;
			for(k=0; js+k<je && ks+k<J.size() && (ks+k<js || je<=ks); ++k)
				if( J[js+k] != J[ks+k] )
					break;
			if( k==0 )
				continue;

			// we have J[js, js+k)+J[js+k, je) in J, so we want              m in B
			//         J[ks, ks+k)                              J[js+k,je) + m
			string m = findInB(J_sub(js+k,je));
			if( !m.empty() )
				update(&result, jsub(js,je)+m);
		}
		return result;
	}

	// O(|J|^2 |B|^2) in total
	map<J_sub, string> memo_fib;
	string findInB(J_sub key)
	{
		if( memo_fib.count(key) )
			return memo_fib[key];

		string result;
		for(string::iterator it=B.begin(); it!=B.end(); ++it) // for each B[ks,ke)==key
		{
			it = search(it, B.end(), J.begin()+key.first, J.begin()+key.second);
			if( it == B.end() )
				break;
			B_index ks = it - B.begin();
			B_index ke = ks + (key.second - key.first);

			// try all B[ks, ke)+B[ke, kee), and try to find another B[ke, kee) before ks or after kee
			for(B_index kee=ke+1; kee<=B.size(); ++kee)
				if( canFindBefore(ks, B_sub(ke,kee)) || canFindAfter(kee, B_sub(ke,kee)) )
					update(&result, bsub(ke,kee));
		}
		return memo_fib[key] = result;
	}

	// O(|B|^4) in total : for each substring m of B, the first and last occurence is memoized
	bool canFindBefore(B_index bi, B_sub m) { return firstOccurence(m)+(m.second-m.first) <= bi; }
	bool canFindAfter (B_index bi, B_sub m) { return bi <= lastOccurence(m)-(m.second-m.first); }

	map<B_sub, B_index> memo_fo;
	B_index firstOccurence(B_sub m)
	{
		if( memo_fo.count(m) )
			return memo_fo[m];
		return memo_fo[m] = search(B.begin(), B.end(), B.begin()+m.first, B.begin()+m.second)-B.begin();
	}

	map<B_sub, B_index> memo_lo;
	B_index lastOccurence(B_sub m)
	{
		if( memo_lo.count(m) )
			return memo_lo[m];
		int mrs = B.size() - m.second;
		int mre = B.size() - m.first;
		return memo_lo[m] = B.size() - (search(B.rbegin(), B.rend(), B.rbegin()+mrs, B.rbegin()+mre)-B.rbegin());
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, TheBoringStoreDivOne().find(J, B));}
int main(){

CASE(0)
	string J = "StoreOfJohn"; 
	string B = "StoreOfBrus"; 
	string _ = "or"; 
END
CASE(1)
	string J = "JohnAndJohn"; 
	string B = "John"; 
	string _ = ""; 
END
CASE(2)
	string J = "JohnLikesToPlayGames"; 
	string B = "BrusAlsoLikesToPlayGames"; 
	string _ = "esToPlayGames"; 
END
CASE(3)
	string J = "abacaba"; 
	string B = "abacabadabacaba"; 
	string _ = "abaabacaba"; 
END
CASE(4)
	string J = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 
	string B = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 
	string _ = "abacabaabacabaabacabaabacabaabacabaabacabaabacabaab"; 
END
CASE(5)
	string J = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 
	string B = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 
	string _ = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; 
END
}
// END CUT HERE