COUNTPL - Đếm số Palindrome
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define endl '\n'
const int N = 500;
using namespace std;
bool isPalin[N][N];
int f[N], trace[N];
char s[N];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
REP(i, 1, n) isPalin[i][i] = isPalin[i + 1][i] = 1;
REPD(i, n, 1) REP(j, i + 1, n)
isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1];
REP(i, 1, n) {
f[i] = n;
REPD(j, i, 1)
if (isPalin[j][i] && f[i] > f[j - 1]) {
f[i] = f[j - 1] + 1;
trace[i] = j;
}
}
cout << f[n] << endl;
/*
vector<string> ans;
for (int i = n; i; i = trace[i] - 1) {
string palin = "";
REP(j, trace[i], i) palin += s[j];
ans.push_back(palin);
}
reverse(ans.begin(), ans.end());
for(vector<string>::iterator it = ans.begin(); it != ans.end(); ++it)
cout << *it << endl;
*/
return 0;
}