Advertisement
skb50bd

Longest Palindromic Subsequence

Oct 29th, 2016
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <windows.h>
  5. #define TAB 3
  6. #define SIZE 100
  7. #define fRED 0xFC
  8. #define fBLACK 0xF0
  9.  
  10. using namespace std;
  11.  
  12. int C[SIZE][SIZE];
  13.  
  14. void color (unsigned short v) {
  15.     HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);
  16.     SetConsoleTextAttribute(hcon, v);
  17. }
  18.  
  19. int max (int x, int y) {
  20.     return x > y ? x : y;
  21. }
  22.  
  23. void LPS (string X, int N) {
  24.     for (int i = 0; i < N; i++)
  25.         C[i][i] = 1;
  26.  
  27.     for (int Len = 2; Len <= N; Len++)
  28.         for (int i = 0, j; i <= N - Len; i++) {
  29.             j = i + Len - 1;
  30.             if (X[i] == X[j]) {
  31.                 if (i == j - 1)
  32.                     C[i][j] = 2;
  33.                 else
  34.                     C[i][j] = 2 + C[i + 1][j - 1];
  35.             }
  36.             else
  37.                 C[i][j] = max (C[i + 1][j], C[i][j - 1]);
  38.         }
  39. }
  40.  
  41.  
  42. string getLPS (string X, int N) {
  43.     char P[SIZE];
  44.  
  45.     int i = 0, j = N - 1;
  46.     int x = 0, y = C[0][N - 1] - 1;
  47.  
  48.     while (C[i][j]) {
  49.         if (C[i][j] == 1) {
  50.             P[x++] = X[i];
  51.             P[y--] = X[j];
  52.             break;
  53.         }
  54.         else if (C[i][j] > C[i][j - 1] && C[i][j] > C[i + 1][j]) {
  55.             P[x++] = X[i++];
  56.             P[y--] = X[j--];
  57.         }
  58.         else if (C[i][j] == C[i + 1][j])
  59.             i++;
  60.         else if (C[i][j] == C[i][j - 1])
  61.             j--;
  62.     }
  63.     P[C[0][N - 1]] = '\0';
  64.  
  65.     return P;
  66. }
  67.  
  68.  
  69. void print_Table(string X, int N) {
  70.     cout << "LPS Table: " << endl;
  71.     for (int i = 0; i < N; i++)
  72.         cout << setw(TAB) << i;
  73.     cout << endl;
  74.     color(fRED);
  75.     for (int i = 0; X[i]; i++)
  76.         cout << setw(TAB) << X[i];
  77.     color(fBLACK);
  78.     cout << endl;
  79.     for (int i = 0; i < N; i++) {
  80.         for (int j = 0; j < N; j++) {
  81.             if (C[i][j])
  82.                 cout << setw(TAB) << C[i][j];
  83.             else
  84.                 cout << setw(TAB) << "-";
  85.         }
  86.         color(fRED);
  87.         cout << setw(TAB) << X[i];
  88.         color(fBLACK);
  89.         cout << setw(TAB) << i;
  90.         cout << endl;
  91.     }
  92.     cout << endl;
  93. }
  94.  
  95.  
  96.  
  97. int main() {
  98.     string X;
  99.     cout << "String: ";
  100.     color (fRED);
  101.     getline(cin, X);
  102.     color (fBLACK);
  103.     int N = X.length();
  104.  
  105.     LPS (X, N);
  106.     cout << "Length of LPS: ";
  107.     color (fRED);
  108.     cout << C[0][N - 1] << endl;
  109.     color (fBLACK);
  110.     cout << "LPS: ";
  111.     color (fRED);
  112.     cout << getLPS(X, N) << endl;
  113.     color (fBLACK);
  114.  
  115.     print_Table(X, N);
  116.  
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement