Created
September 15, 2018 06:50
-
-
Save completejavascript/4b19ac496598912289f19445e46950e9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
const int MAX = 105; | |
char S1[MAX], S2[MAX]; | |
int Leng1, Leng2; | |
int L[MAX][MAX]; // L[i][j] là độ dài LCS của S1[1..i] và S2[1...j] | |
char Common[MAX][MAX][MAX]; // Lưu thành phần chung dài nhất với L[i][j] trên. | |
char Result[2*MAX]; // Lưu kết quả | |
int Leng; // Độ dài mảng kết quả | |
/* | |
* Trả về độ dài xâu s | |
*/ | |
int GetLeng(char *s) | |
{ | |
int leng = 0; | |
while(s[leng] != '\0') leng++; | |
return leng; | |
} | |
/* | |
* Sao chép xâu src với độ dài leng vào xâu dst | |
*/ | |
void CpyStr(char *dst, char *src, int leng) | |
{ | |
for(int i = 0; i < leng; i++) | |
dst[i] = src[i]; | |
dst[leng] = '\0'; | |
} | |
int main(int argc, char** argv) | |
{ | |
ios::sync_with_stdio(false); | |
//freopen("input.txt", "r", stdin); | |
cin >> S1; | |
while(true) | |
{ | |
// Nhập xâu S1, S2 và tính độ dài của nó | |
cin >> S2; | |
Leng1 = GetLeng(S1); | |
Leng2 = GetLeng(S2); | |
// Trường hợp cơ sở | |
for(int i = 0; i <= Leng1; i++) | |
L[i][0] = 0; | |
for(int j = 0; j <= Leng2; j++) | |
L[0][j] = 0; | |
for(int i = 1; i <= Leng1; i++) | |
for(int j = 1; j <= Leng2; j++) | |
{ | |
// Chỉ số mảng char* tính từ 0 | |
// Nếu hai kí tự đang xét giống nhau | |
// thì cho vào dãy chung tăng dài nhất | |
if(S1[i-1] == S2[j-1]) | |
{ | |
L[i][j] = 1 + L[i-1][j-1]; | |
CpyStr(Common[i][j], Common[i-1][j-1], L[i-1][j-1]); | |
Common[i][j][L[i][j] - 1] = S1[i - 1]; | |
Common[i][j][L[i][j]] = '\0'; | |
} | |
else // S1[i-1] != S2[j-1] thì giữ lại dãy nào có độ dài lớn hơn | |
{ | |
// Chọn thành phần lớn hơn | |
if(L[i-1][j] > L[i][j-1]) | |
{ | |
L[i][j] = L[i-1][j]; | |
CpyStr(Common[i][j], Common[i-1][j], L[i-1][j]); | |
} | |
else | |
{ | |
L[i][j] = L[i][j-1]; | |
CpyStr(Common[i][j], Common[i][j-1], L[i][j-1]); | |
} | |
} | |
} | |
// In kết quả | |
int i1 = 0; // Con trỏ vào đầu s1 | |
int i2 = 0; // Con trỏ vào đầu s2 | |
int c = 0; // Con trỏ vào đầu xâu common[Leng1][Leng2] | |
Leng = 0; | |
while(Common[Leng1][Leng2][c] != '\0') | |
{ | |
// In ra thành phần ở S1 cho đến thành phần chung | |
while(S1[i1] != Common[Leng1][Leng2][c]) | |
Result[Leng++] = S1[i1++]; | |
// In ra thành phần sở S2 cho đến thành phần chung | |
while (S2[i2] != Common[Leng1][Leng2][c]) | |
Result[Leng++] = S2[i2++]; | |
// In ra thành phần chung, rồi tăng con trỏ lên và tiếp tục | |
Result[Leng++] = Common[Leng1][Leng2][c]; | |
c += 1; | |
i1 += 1; | |
i2 += 1; | |
} | |
// Sau khi in hết thành phần chung rồi, thì in nốt S1 rồi S2 | |
for(int i = i1; i < Leng1; i++) | |
Result[Leng++] = S1[i]; | |
for(int i = i2; i < Leng2; i++) | |
Result[Leng++] = S2[i]; | |
Result[Leng] = '\0'; | |
cout << Result << endl; | |
if(!(cin >> S1)) break; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment