#include <cstdio> #include <iostream> #include <map> #include <string> using namespace std; int c[300][300], b[300][300], print1[300], print2[300]; int printer(int i, int j, int *x, int *print) { int k=0; while (i>0 || j>0) { if (b[i][j]==1) { print[k++]=x[i]; i--; j--; } else if (b[i][j]==2) { i--; } else { j--; } } return k; } int lcs(int *x, int *y, int size_a, int size_b) { int m = size_a, n = size_b, i, j; for (i=0 ; i<=m ; i++) { for (j=0 ; j<=n ; j++) { c[i][j]=b[i][j]=0; } } for (i=1 ; i<m ; i++) { for (j=1 ; j<n ; j++) { if (x[i]==y[j]) { c[i][j] = c[i-1][j-1]+1; b[i][j]=1; } else { if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } } return c[i-1][j-1]; } class v { public: string word; int id; }; string s; int main() { while (1) { if (cin >> s) { map<string,int>l1; v wordList[300]={"",0}; int i, l1_count=1, seq1_len=1, seq2_len=1, sizer, size1, size2, *print; int seq1[200], seq2[200]; l1[s]=l1_count; wordList[l1_count].id = l1_count; wordList[l1_count].word=s; seq1[ seq1_len++ ] = l1_count++; while (cin >> s && s!="#") { if (l1[s]) { seq1[ seq1_len++ ] = l1[s]; } else { l1[ s ] = l1_count; wordList[l1_count].id = l1_count; wordList[l1_count].word = s; seq1[ seq1_len++ ] = l1_count++; } } while (cin >> s && s!="#") { if (l1[s]) { seq2[ seq2_len++ ] = l1[s]; } else { l1[ s ] = l1_count; wordList[l1_count].id = l1_count; wordList[l1_count].word = s; seq2[ seq2_len++ ] = l1_count++; } } size1 = lcs(seq1,seq2,seq1_len,seq2_len); printer(seq1_len-1,seq2_len-1, seq1, print1); size2 = lcs(seq2,seq1,seq2_len,seq1_len); printer(seq2_len-1,seq1_len-1, seq2, print2); if (size1>size2) { print = &print1[0]; sizer=size1; } else { print = &print2[0]; sizer=size2; } for (i=sizer-1 ; i>0 ; i--) { cout << wordList[print[i]].word << " "; } cout << wordList[print[i]].word << endl; } else { break; } } return 0; }
Friday, September 30, 2011
[UVa] 531 - Compromise
Critical case: Normally you'd just check Part 1 against Part 2. But checking Part 2 agianst Part 1 might yield a better result.
Subscribe to:
Post Comments (Atom)
Connect Rapoo MT750S with Linux (Tested on Manjaro)
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...
-
I like coding a lot, keeps me glued to the PC for hours. For that reason it's a need to edit the Syntax Highlighter to suit my eyes for...
-
I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...
-
Install MinGW GCC Port on Windows. 1. Just go to this address [ http://sourceforge.net/projects/mingw/files/Installer/mingw-get-inst/ ]...
I wish I could understand that code. :'(
ReplyDeletePlease point out which points confuse you so that I can help you. If you do not understand the coding language used here altogether, then you should first learn C/C++.
ReplyDelete