- #include <bits/stdc++.h>
- using namespace std;
- #define For(i,a) for(int i=0;i<a;++i)
- #define foreach(x,v) for(typeof (v).begin() x = (v).begin(); x!= (v).end(); x++)
- #define all(x) x.begin(),x.end()
- #define rall(x) x.rbegin(),x.rend()
- #define D(x) cout<< #x " = "<<(x)<<endl
- #define Dbg if(1)
- #define MAXNODES 1000
- int dp[101][101];
- string lex[101][101];
- int lcs(const string &a,const string &b, string &ans){
- int n=a.size(),m=b.size();
- if(n==0 || m==0) return 0;
- for(int i=0;i<=n;++i){
- dp[i][0] = 0;
- lex[i][0].clear();
- }
- for(int j=0;j<=m;++j){
- dp[0][j] = 0;
- lex[0][j].clear();
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;++j){
- if(a[i-1]==b[j-1]){
- dp[i][j] = dp[i-1][j-1]+1;
- lex[i][j] = lex[i-1][j-1] + a[i-1];
- }
- else if(dp[i][j-1] > dp[i-1][j]){
- dp[i][j] = dp[i][j-1];
- lex[i][j] = lex[i][j-1];
- }else if(dp[i][j-1] < dp[i-1][j]){
- dp[i][j] = dp[i-1][j];
- lex[i][j] = lex[i-1][j];
- }else{
- dp[i][j] = dp[i-1][j];
- lex[i][j] = min(lex[i-1][j],lex[i][j-1]);
- }
- }
- }
- ans=lex[n][m];
- return dp[n][m];
- }
- int main(){
- int numcas;cin>>numcas;
- for(int cid=1;cid<=numcas;++cid){
- string a,b;cin>>a>>b;
- string ans;
- cout<<"Case "<<cid<<": "<<((lcs(a,b,ans)==0)?":(":ans)<<endl;
- }
- return 0;
- }
- /*
- // another implementation
- #include <bits/stdc++.h>
- using namespace std;
- #define N 100
- int L[N][N];
- set<string> findLCS(string X, string Y, int m, int n){
- set<string> s;
- if (m == 0 || n == 0){
- s.insert("");
- return s;
- }
- if (X[m - 1] == Y[n - 1]){
- set<string> tmp = findLCS(X, Y, m - 1, n - 1);
- for (string str : tmp)
- s.insert(str + X[m - 1]);
- }
- else{
- if (L[m - 1][n] >= L[m][n - 1])
- s = findLCS(X, Y, m - 1, n);
- if (L[m][n - 1] >= L[m - 1][n]){
- set<string> tmp = findLCS(X, Y, m, n - 1);
- s.insert(tmp.begin(), tmp.end());
- }
- }
- return s;
- }
- int LCS(string X, string Y, int m, int n){
- for (int i = 0; i <= m; i++){
- for (int j = 0; j <= n; j++){
- if (i == 0 || j == 0)
- L[i][j] = 0;
- else if (X[i - 1] == Y[j - 1])
- L[i][j] = L[i - 1][j - 1] + 1;
- else
- L[i][j] = max(L[i - 1][j], L[i][j - 1]);
- }
- }
- return L[m][n];
- }
- int main(){
- int ts;
- cin>>ts;
- for(int k = 1; k <= ts; k++){
- string X;
- string Y;
- cin>>X>>Y;
- int m = X.length();
- int n = Y.length();
- //cout << "LCS length is " << LCS(X, Y, m, n) << endl;
- set<string> s = findLCS(X, Y, m, n);
- set<string> :: iterator p;
- p = s.begin();
- if((*p) == "") printf("Case %d: :(\n", k);
- else printf("Case %d: %s\n", k, (*p).c_str());
- s.clear();
- }
- return 0;
- }
- */
No comments:
Post a Comment