Submission #10405612

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(t) for(ll i =0;i<t;i++)
#define bs(a,x) binary_search(a.begin(),a.end(),x)
#define ll long long int
#define ul unsigned long int
#define ld long double
#define umpi unordered_map<int,int> 
#define umpl unordered_map<ll,ll> 
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define mod 1000000007 
#define N 10000000
#define all(a) a.begin(),a.end()
#define point pair<ll,ll>

const int inf = 1000000007;
const ll linf = 1ll * inf * inf;
const ll MAXIMUM =1000005;

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll max(ll a, ll b){return a>b?a:b;}
inline ll min(ll a, ll b){return a<b?a:b;}

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

string to_str(char a)
{
    string s(1,a);
    return s;
}

int main()
{
	fio;
	string s,t;cin>>s>>t;
	pair<ll,string> dp[s.length()+1][t.length()+1];
	for(int i=0;i<=s.length();i++)
	{
		for(int j=0;j<=t.length();j++)
		{
			dp[i][j].first=0;
		}
	}
	for(int i=1;i<=s.length();i++)
	{
		for(int j=1;j<=t.length();j++)
		{
			if(s[i-1]==t[j-1])
			{
				if((dp[i-1][j-1].first+1)>=dp[i][j].first)
				{
					dp[i][j].first=dp[i-1][j-1].first+1;
					dp[i][j].second=dp[i-1][j-1].second+to_str(s[i-1]);
				}
			}
			if(dp[i-1][j].first>=dp[i][j].first)
			{
				dp[i][j].first=dp[i-1][j].first;
				dp[i][j].second=dp[i-1][j].second;
			}
			if(dp[i][j-1].first>=dp[i][j].first)
			{
				dp[i][j].first=dp[i][j-1].first;
				dp[i][j].second=dp[i][j-1].second;
			}			
		}
	}
	ll ans=-1;
	string temp;
	for(int i=0;i<=s.length();i++)
	{
		for(int j=0;j<=t.length();j++)
		{
			if(dp[i][j].first>ans)
			{
				ans=dp[i][j].first;
				temp=dp[i][j].second;
				// cout<<dp[i][j].first<<" "<<dp[i][j].second<<"   ";
			}
			// cout<<endl;
		}
	}
	// cout<<ans<<"\n";
	cout<<temp<<"\n";
}

Submission Info

Judge Result