TOPALIN - Palindrome String
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
#include <cstring>
struct chu
{
int so,a[150];
};
int tong,maxx;
int n,c[150][150],d[150],flag[150],KQ = 0;
char s[100010];
chu A[150];
void duyet(int x)
{
flag[x] = 1;
tong += d[x];
if(d[x]>maxx)
maxx = d[x];
for(int i = 1;i<=A[x].so;i++)
if(!flag[A[x].a[i]])
duyet(A[x].a[i]);
}
int main()
{
scanf("%s",s);
n = strlen(s);
for(int i = 0;i<150;i++)
{
A[i].so = 0;
flag[i] = 0;
for(int j = 0;j<150;j++)
c[i][j] = 0;
}
for(int i = 0;i<=(n-1)/2;i++)
{
if(i*2==n-1)
d[s[i]]++;
else
{
d[s[i]]++;
d[s[n-1-i]]++;
if(s[i]!=s[n-1-i]&& !c[s[i]][s[n-1-i]])
{
c[s[i]][s[n-1-i]]=1;
c[s[n-1-i]][s[i]]=1;
A[s[i]].a[++A[s[i]].so] = s[n-1-i];
A[s[n-1-i]].a[++A[s[n-1-i]].so] = s[i];
}
}
}
for(int i = '0';i<='z';i++)
{
if(flag[i] || !d[i])
continue;
else
{
tong = 0;
maxx = 0;
duyet(i);
KQ += (tong-maxx);
}
}
printf("%d",KQ);
//getch();
}