NKPALIN - Chuỗi đối xứng
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define SZ 2005
#define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i )
#define max(a, b) ((a) > (b) ? (a) : (b))
char s[SZ];
int f[SZ][SZ], n;
void solve() {
FOR( len, 1, n ) FOR( i, 0, n-len ) {
int j = i + len - 1;
if ( len == 1 ) f[i][j] = 1;
//else if ( len == 2 ) f[i][j] = s[i] == s[j] ? 2 : max(f[i][j], f[j][j]);
else f[i][j] = s[i] == s[j] ? f[i+1][j-1] + 2 : max(f[i][j-1], f[i+1][j]);
/*printf( "%d %d %d\n", len, i, j);
FOR(i, 0, n-1) {
FOR(j, 0, n-1) printf( "%3d", f[i][j] );
putchar('\n');
}*/
}
}
void print() {
char res[SZ]; memset(res, '\0', sizeof res);
int i = 0, j = n-1, l = 0;
while( i <= j ) {
if ( f[i][j] == f[i+1][j] ) ++i;
else if ( f[i][j] == f[i][j-1] ) --j;
else {
res[l++] = s[i];
++i; --j;
}
}
printf( "%s", res );
if( f[0][n-1] % 2 ) res[--l] = 0;
reverse(res, res+l);
puts(res);
}
int main() {
scanf( "%s", s ); n = strlen(s);
solve();
print();
return 0;
}