QBPAL - Đếm chuỗi đối xứng
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
//#include <conio.h>
#define base 100000000
struct solon
{
int so;
int a[40];
};
solon f[122][122],T;
char s[122];
int n;
solon tong (solon A,solon B)
{
int du = 0;
solon C;
if(A.so<B.so)
{
C = A;
A = B;
B = C;
}
for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++)
{
C.a[i] = (A.a[i]+B.a[i]+du)%base;
du = (A.a[i]+B.a[i]+du)/base;
}
if(du>0) {C.so++; C.a[C.so] = du;}
return C;
}
solon hieu(solon A,solon B)
{
int du = 0;
solon C;
for(int i = B.so+1;i<=A.so;i++) B.a[i] = 0;
C.so = A.so;
for(int i = 1;i<=A.so;i++)
{
C.a[i] = (A.a[i]-B.a[i]-du);
if(C.a[i]<0) {
C.a[i] += base;
du = 1;
}
}
while(C.a[C.so]==0 && C.so>1) C.so--;
return C;
}
void print(solon A)
{
printf("%d",A.a[A.so]);
for(int i = A.so-1;i>=1;i--)
printf("%08d",A.a[i]);
}
bool doixung(int i,int j)
{
if(j-i<2)
return (s[i]==s[j]);
if(s[i]!=s[j]) return false;
else return doixung(i+1,j-1);
}
int main()
{
// freopen("QBPAL.in","r",stdin);
scanf("%s",s);
n = strlen(s);
T.so = 1; T.a[1] = 1;
for(int i = 0;i<n;i++)
{
f[i][i] = T;
f[i+1][i].so = 1;
f[i+1][i].a[1] = 0;
}
for(int k = 1;k<n;k++)
for(int i =0;i+k<n;i++)
{
int j = i+k;
f[i][j] = tong(f[i+1][j],f[i][j-1]);
if(s[i]==s[j]) f[i][j] = tong(f[i][j],T);
else f[i][j] = hieu(f[i][j],f[i+1][j-1]);
// printf("%d %d %d\n",i,j,f[i][j].a[1]);
}
//if(doixung(0,n-1)) f[0][n-1] = hieu(f[0][n-1],T);
print(f[0][n-1]);
// getch();
}