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;
}

Download