Advertisement
skb50bd

Longest Common Substring

Oct 27th, 2016
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <iomanip>
  4. #define SIZE 100
  5. using namespace std;
  6.  
  7. int B[SIZE][SIZE], C[SIZE][SIZE];
  8.  
  9. void LCS_length (string X, string Y, int m, int n, int &hi, int &hix, int &hiy) {
  10.     for (int i = 1; i <= m; i++)
  11.         C[i][0] = 0;
  12.     for (int i = 0; i <= n; i++)
  13.         C[0][i] = 0;
  14.     for (int i = 1; i <= m; i++)
  15.         for (int j = 1; j <= n; j++) {
  16.             if (X[i - 1] == Y[j - 1]) {
  17.                 C[i][j] = 1 + C[i - 1][j - 1];
  18.                 B[i][j] = 1;
  19.             }
  20.             else {
  21.                 C[i][j] = 0;
  22.                 B[i][j] = 0;
  23.             }
  24.         }
  25.  
  26.     hi = hix = hiy = 0;
  27.     for (int i = 1; i <= m; i++)
  28.         for (int j = 1; j <=n; j++)
  29.             if (C[i][j] > hi) {
  30.                 hi = C[i][j];
  31.                 hix = i;
  32.                 hiy = j;
  33.             }
  34. }
  35.  
  36.  
  37. void print_LCS(string X, int i, int j) {
  38.     if ( i == 0 || j == 0)
  39.         return;
  40.     if (B[i][j] == 1) {
  41.         print_LCS(X, i - 1, j - 1);
  42.         cout << X[i - 1];
  43.     }
  44.     else
  45.         return;
  46. }
  47.  
  48. void print_Table (string X, string Y, int m, int n) {
  49.     cout << "C Table: " << endl;
  50.     cout << setw(6) << "";
  51.     for (int i = 0; i <= n; i++)
  52.         cout << setw(3) << i;
  53.     cout << endl;
  54.     cout << setw(9) << "";
  55.     for (int i = 0; Y[i]; i++)
  56.         cout << setw(3) << Y[i];
  57.     cout << endl;
  58.     for (int i = 0; i <= m; i++) {
  59.         cout << setw(3) << i;
  60.         if (i == 0)
  61.             cout << setw(3) << "";
  62.         else
  63.             cout << setw(3) << X[i - 1];
  64.         for (int j = 0; j <= n; j++)
  65.             cout << setw(3) << C[i][j];
  66.         cout << endl;
  67.     }
  68.     cout << endl;
  69.  
  70.     cout << "B Table: " << endl;
  71.     cout << setw(6) << "";
  72.     for (int i = 1; i <= n; i++)
  73.         cout << setw(3) << i;
  74.     cout << endl;
  75.     cout << setw(6) << "";
  76.     for (int i = 0; Y[i]; i++)
  77.         cout << setw(3) << Y[i];
  78.     cout << endl;
  79.     for (int i = 1; i <= m; i++) {
  80.         cout << setw(3) << i;
  81.         if (i == 0)
  82.             cout << setw(3) << "";
  83.         else
  84.             cout << setw(3) << X[i - 1];
  85.         for (int j = 1; j <= n; j++)
  86.             cout << setw(3) << B[i][j];
  87.         cout << endl;
  88.     }
  89.     cout << endl;
  90. }
  91.  
  92.  
  93. int main() {
  94.     string X, Y;
  95.     cout << "String X: ";
  96.     cin >> X;
  97.     cout << "String Y: ";
  98.     cin >> Y;
  99.     int m, n;
  100.     m = X.length();
  101.     n = Y.length();
  102.     int hi, hix, hiy;
  103.     LCS_length(X, Y, m, n, hi, hix, hiy);
  104.     cout << "LCS Length: " << hi << endl;
  105.     cout << "LCS: ";
  106.     print_LCS(X, hix, hiy);
  107.     cout << endl << endl;
  108.  
  109.     print_Table(X, Y, m, n);
  110.  
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement