|
1 | | -/************************************* |
| 1 | +/* _ |
| 2 | + * _|_ o._ o._ __|_| _. _|_ |
| 3 | + * _>| ||| ||| |(_|| |(_|_>| | |
| 4 | + * _| |
| 5 | + * @author Amirul islam Al Mamun |
2 | 6 | * An Easy LCS LightOJ - 1110 >> DP |
3 | | - * @author Amirul Islam (shiningflash) |
4 | | - ************************************/ |
| 7 | + */ |
5 | 8 |
|
6 | | -#include <cstdio> |
7 | | -#include <iomanip> |
8 | | -#include <cstring> |
9 | | -#include <cmath> |
10 | | -#include <cstdlib> |
11 | | -#include <cctype> |
12 | | -#include <algorithm> |
13 | | -#include <string> |
14 | | -#include <vector> |
15 | | -#include <queue> |
16 | | -#include <map> |
17 | | -#include <set> |
18 | | -#include <sstream> |
19 | | -#include <stack> |
20 | | -#include <list> |
21 | | -#include <iostream> |
22 | | -#include <assert.h> |
23 | | - |
24 | | -#define mem(x,y) memset(x,y,sizeof(x)) |
25 | | -#define CLEAR(x) memset(x,0,sizeof(x)) |
26 | | - |
27 | | -#define pb push_back |
28 | | -#define Sort(v) sort(v.begin(),v.end()) |
29 | | -#define _sort(s, n) sort(s, s+n) |
30 | | -#define sqr(x) ((x)*(x)) |
31 | | - |
32 | | -#define le 50001 |
33 | | -#define ERR 1e-9 |
34 | | -#define pi (2*acos(0)) |
35 | | -#define PI 3.141592653589793 |
36 | | - |
37 | | -#define scanint(a) scanf("%d",&a) |
38 | | -#define scanLLD(a) scanf("%lld",&a) |
39 | | - |
40 | | -typedef unsigned long long ll; |
| 9 | +#include <bits/stdc++.h> |
41 | 10 | using namespace std; |
42 | 11 |
|
43 | | -/**********************End*******************/ |
44 | | - |
45 | | -string s1, s2; |
46 | | -int cost[105][105], path[105][105], lcs[105]; |
47 | | -int t, l1, l2, lcs_len; |
| 12 | +const int mx = 1e3; |
48 | 13 |
|
49 | | -inline void LCS_LENGTH() { |
50 | | - for (int i = 1; i <= l1; cost[i][0] = 0, i++); |
51 | | - for (int j = 1; j <= l2; cost[0][j] = 0, j++); |
| 14 | +int path[mx][mx], cost[mx][mx]; |
52 | 15 |
|
53 | | - for (int i = 1; i <= l1; i++) { |
54 | | - for (int j = 1; j <= l2; j++) { |
| 16 | +int lcs(string s1, string s2) { |
| 17 | + for (int i = 1; i <= s1.length(); i++) { |
| 18 | + for (int j = 1; j <= s2.length(); j++) { |
| 19 | + // common word |
55 | 20 | if (s1[i-1] == s2[j-1]) { |
56 | 21 | cost[i][j] = cost[i-1][j-1] + 1; |
57 | 22 | path[i][j] = 1; |
58 | 23 | } |
| 24 | + // UP greater |
59 | 25 | else if (cost[i-1][j] >= cost[i][j-1]) { |
60 | 26 | cost[i][j] = cost[i-1][j]; |
61 | 27 | path[i][j] = 2; |
62 | 28 | } |
| 29 | + // LEFT greater |
63 | 30 | else { |
64 | 31 | cost[i][j] = cost[i][j-1]; |
65 | 32 | path[i][j] = 3; |
66 | 33 | } |
67 | 34 | } |
68 | 35 | } |
69 | | - lcs_len = cost[l1][l2]; |
| 36 | + returncost[s1.length()][s2.length()]; |
70 | 37 | } |
71 | 38 |
|
72 | | -inline void LCS() { |
73 | | - int i = l1, j = l2, k = lcs_len-1; |
74 | | - while (k >= 0) { |
| 39 | +string get_lcs_string(string s1, string s2, int lcs_len) { |
| 40 | + // no common substring |
| 41 | + if (lcs_len == 0) { |
| 42 | + return ":("; |
| 43 | + } |
| 44 | + |
| 45 | + int i = s1.length(); |
| 46 | + int j = s2.length(); |
| 47 | + int k = lcs_len; |
| 48 | + |
| 49 | + stack <char> st; |
| 50 | + |
| 51 | + while (k > 0) { |
75 | 52 | if (path[i][j] == 1) { |
76 | | - lcs[k] = s1[i-1]; |
77 | | - i--; j--; k--; |
| 53 | + st.push(s1[i-1]); |
| 54 | + i--; |
| 55 | + j--; |
| 56 | + k--; |
| 57 | + } |
| 58 | + else if (path[i][j] == 2) { |
| 59 | + i--; |
| 60 | + } |
| 61 | + else { |
| 62 | + j--; |
78 | 63 | } |
79 | | - else if (path[i][j] == 2) i--; |
80 | | - else if (path[i][j] == 3) j--; |
81 | 64 | } |
82 | | -} |
83 | 65 |
|
84 | | -inline void LCS_PRINT() { |
85 | | - if (lcs_len <= 0) cout << ":("; |
86 | | - else |
87 | | - for (int i = 0; i < lcs_len; i++) |
88 | | - cout << (char) lcs[i]; |
89 | | - cout << endl; |
| 66 | + string lcs_str = ""; |
| 67 | + while (!st.empty()) { |
| 68 | + lcs_str.push_back((char) st.top()); |
| 69 | + st.pop(); |
| 70 | + } |
| 71 | + |
| 72 | + return lcs_str; |
90 | 73 | } |
91 | 74 |
|
92 | 75 | int main() { |
93 | | - scanint(t); |
94 | | - for (int i = 1; i <= t; i++) { |
95 | | - cin >> s1 >> s2; |
96 | | - l1 = s1.length(); l2 = s2.length(); |
97 | | - LCS_LENGTH(); |
98 | | - LCS(); |
99 | | - cout << "Case " << i << ": "; |
100 | | - LCS_PRINT(); |
101 | | - } |
| 76 | + string s1, s2; |
| 77 | + cin >> s1 >> s2; |
| 78 | + int lcs_len = lcs(s1, s2); |
| 79 | + cout << get_lcs_string(s1, s2, lcs_len) << endl; |
| 80 | + return 0; |
102 | 81 | } |
0 commit comments