Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <iomanip>
- #define SIZE 100
- using namespace std;
- int B[SIZE][SIZE], C[SIZE][SIZE];
- void LCS_length (string X, string Y, int m, int n, int &hi, int &hix, int &hiy) {
- for (int i = 1; i <= m; i++)
- C[i][0] = 0;
- for (int i = 0; i <= n; i++)
- C[0][i] = 0;
- for (int i = 1; i <= m; i++)
- for (int j = 1; j <= n; j++) {
- if (X[i - 1] == Y[j - 1]) {
- C[i][j] = 1 + C[i - 1][j - 1];
- B[i][j] = 1;
- }
- else {
- C[i][j] = 0;
- B[i][j] = 0;
- }
- }
- hi = hix = hiy = 0;
- for (int i = 1; i <= m; i++)
- for (int j = 1; j <=n; j++)
- if (C[i][j] > hi) {
- hi = C[i][j];
- hix = i;
- hiy = j;
- }
- }
- void print_LCS(string X, int i, int j) {
- if ( i == 0 || j == 0)
- return;
- if (B[i][j] == 1) {
- print_LCS(X, i - 1, j - 1);
- cout << X[i - 1];
- }
- else
- return;
- }
- void print_Table (string X, string Y, int m, int n) {
- cout << "C Table: " << endl;
- cout << setw(6) << "";
- for (int i = 0; i <= n; i++)
- cout << setw(3) << i;
- cout << endl;
- cout << setw(9) << "";
- for (int i = 0; Y[i]; i++)
- cout << setw(3) << Y[i];
- cout << endl;
- for (int i = 0; i <= m; i++) {
- cout << setw(3) << i;
- if (i == 0)
- cout << setw(3) << "";
- else
- cout << setw(3) << X[i - 1];
- for (int j = 0; j <= n; j++)
- cout << setw(3) << C[i][j];
- cout << endl;
- }
- cout << endl;
- cout << "B Table: " << endl;
- cout << setw(6) << "";
- for (int i = 1; i <= n; i++)
- cout << setw(3) << i;
- cout << endl;
- cout << setw(6) << "";
- for (int i = 0; Y[i]; i++)
- cout << setw(3) << Y[i];
- cout << endl;
- for (int i = 1; i <= m; i++) {
- cout << setw(3) << i;
- if (i == 0)
- cout << setw(3) << "";
- else
- cout << setw(3) << X[i - 1];
- for (int j = 1; j <= n; j++)
- cout << setw(3) << B[i][j];
- cout << endl;
- }
- cout << endl;
- }
- int main() {
- string X, Y;
- cout << "String X: ";
- cin >> X;
- cout << "String Y: ";
- cin >> Y;
- int m, n;
- m = X.length();
- n = Y.length();
- int hi, hix, hiy;
- LCS_length(X, Y, m, n, hi, hix, hiy);
- cout << "LCS Length: " << hi << endl;
- cout << "LCS: ";
- print_LCS(X, hix, hiy);
- cout << endl << endl;
- print_Table(X, Y, m, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement