Palindromic Subsequence
| Palindromic Subsequence |
A Subsequence is a sequence obtained by deleting zero or more characters in a string. A Palindrome is a string which when read from left to right, reads same as when read from right to left. Given a string, find the longest palindromic subsequence. If there are many answers to it, print the one that comes lexicographically earliest.
Constraints
- Maximum length of string is 1000.
- Each string has characters `a' to `z' only.
Input
Input consists of several strings, each in a separate line. Input is terminated by EOF.
Output
For each line in the input, print the output in a single line.
Sample Input
aabbaabb computer abzla samhita
Sample Output
aabbaa c aba aha
----------------------------
-----------------------------
wa
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1111];
char b[1111];
int f[1111][1111];
char ans[1111];
int cnt;
struct ANP
{
int x;
int y;
char c;
} p[1111][1111];
int main()
{
while (cin>>(a+1))
{
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
memset(ans,0,sizeof(ans));
memset(p,0,sizeof(p));
cnt=0;
int len=strlen(a+1);
for (int i=1; i<=len; i++)
{
b[len-i+1]=a[i];
}
b[len+1]='\0';
for (int i=1; i<=len; i++)
{
for (int j=1; j<=len; j++)
{
if (a[i]==b[j])
{
f[i][j]=f[i-1][j-1]+1;
p[i][j].x=i-1;
p[i][j].y=j-1;
p[i][j].c=a[i];
}
else
{
if (f[i-1][j]>f[i][j-1])
{
f[i][j]=f[i-1][j];
p[i][j]=p[i-1][j];
}
else if (f[i][j-1]>f[i-1][j])
{
f[i][j]=f[i][j-1];
p[i][j]=p[i][j-1];
}
else
{
f[i][j]=f[i-1][j];
if (p[i-1][j].c<=p[i][j-1].c)
{
p[i][j]=p[i-1][j];
}
else
{
p[i][j]=p[i][j-1];
}
}
}
}
}
int x=len;
int y=len;
while (x!=0&&y!=0)
{
cout<<p[x][y].c;
int tx=p[x][y].x;
int ty=p[x][y].y;
x=tx;
y=ty;
}
cout<<endl;
}
return 0;
}
wa
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1111];
char b[1111];
int f[1111][1111];
char ans[1111];
int cnt;
struct ANP{
int x;
int y;
char c;
}p[1111][1111];
int main()
{
while (cin>>(a+1))
{
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
memset(ans,0,sizeof(ans));
memset(p,0,sizeof(p));
cnt=0;
int len=strlen(a+1);
for (int i=1; i<=len; i++)
{
b[len-i+1]=a[i];
}
b[len+1]='\0';
for (int i=1; i<=len; i++)
{
for (int j=1; j<=len; j++)
{
f[i][j]=f[i-1][j-1];
p[i][j]=p[i-1][j-1];
if (a[i]==b[j])
{
f[i][j]=f[i-1][j-1]+1;
p[i][j].x=i-1;
p[i][j].y=j-1;
p[i][j].c=a[i];
}
else
{
if (f[i-1][j]>f[i][j-1])
{
f[i][j]=f[i-1][j];
p[i][j]=p[i-1][j];
}
else if (f[i][j-1]>f[i-1][j])
{
f[i][j]=f[i][j-1];
p[i][j]=p[i][j-1];
}
else
{
f[i][j]=f[i][j-1];
if (p[i-1][j].c<p[i][j-1].c)
{
p[i][j]=p[i-1][j];
}
else
{
p[i][j]=p[i][j-1];
}
}
}
}
}
int x=len;
int y=len;
while (x!=0&&y!=0)
{
cout<<p[x][y].c;
int tx=p[x][y].x;
int ty=p[x][y].y;
x=tx;
y=ty;
}
cout<<endl;
}
return 0;
}