#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