Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <string>
- #include <windows.h>
- #define TAB 3
- #define SIZE 100
- #define fRED 0xFC
- #define fBLACK 0xF0
- using namespace std;
- int C[SIZE][SIZE];
- void color (unsigned short v) {
- HANDLE hcon = GetStdHandle(STD_OUTPUT_HANDLE);
- SetConsoleTextAttribute(hcon, v);
- }
- int max (int x, int y) {
- return x > y ? x : y;
- }
- void LPS (string X, int N) {
- for (int i = 0; i < N; i++)
- C[i][i] = 1;
- for (int Len = 2; Len <= N; Len++)
- for (int i = 0, j; i <= N - Len; i++) {
- j = i + Len - 1;
- if (X[i] == X[j]) {
- if (i == j - 1)
- C[i][j] = 2;
- else
- C[i][j] = 2 + C[i + 1][j - 1];
- }
- else
- C[i][j] = max (C[i + 1][j], C[i][j - 1]);
- }
- }
- string getLPS (string X, int N) {
- char P[SIZE];
- int i = 0, j = N - 1;
- int x = 0, y = C[0][N - 1] - 1;
- while (C[i][j]) {
- if (C[i][j] == 1) {
- P[x++] = X[i];
- P[y--] = X[j];
- break;
- }
- else if (C[i][j] > C[i][j - 1] && C[i][j] > C[i + 1][j]) {
- P[x++] = X[i++];
- P[y--] = X[j--];
- }
- else if (C[i][j] == C[i + 1][j])
- i++;
- else if (C[i][j] == C[i][j - 1])
- j--;
- }
- P[C[0][N - 1]] = '\0';
- return P;
- }
- void print_Table(string X, int N) {
- cout << "LPS Table: " << endl;
- for (int i = 0; i < N; i++)
- cout << setw(TAB) << i;
- cout << endl;
- color(fRED);
- for (int i = 0; X[i]; i++)
- cout << setw(TAB) << X[i];
- color(fBLACK);
- cout << endl;
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++) {
- if (C[i][j])
- cout << setw(TAB) << C[i][j];
- else
- cout << setw(TAB) << "-";
- }
- color(fRED);
- cout << setw(TAB) << X[i];
- color(fBLACK);
- cout << setw(TAB) << i;
- cout << endl;
- }
- cout << endl;
- }
- int main() {
- string X;
- cout << "String: ";
- color (fRED);
- getline(cin, X);
- color (fBLACK);
- int N = X.length();
- LPS (X, N);
- cout << "Length of LPS: ";
- color (fRED);
- cout << C[0][N - 1] << endl;
- color (fBLACK);
- cout << "LPS: ";
- color (fRED);
- cout << getLPS(X, N) << endl;
- color (fBLACK);
- print_Table(X, N);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement