TOPALIN - Palindrome String
Tác giả: RR
Ngôn ngữ: C++
//Written by RR
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <list>
#include <deque>
#include <cstdio>
#include <cstdlib>
#define MAXN 100111
#define FOR(i,a,b) for(typeof(a) i=a; i<=b; i++)
#define FORD(i,a,b) for(typeof(a) i=a; i>=b; i--)
#define V vector<long>
#define Q queue<long>
#define S set<long>
#define M map<long,long>
#define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define PB push_back
#define SZ(x) ((long) x.size())
#define MP make_pair
#define TWO(x) (long) (1<<x)
#define TWOL(x) (long long) (1<<x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<bool> vb;
typedef pair<long,long> ii;
long n,freq[300];
char s[MAXN];
V ke[300];
long res;
void inp() {
scanf("%s",&s);
n=strlen(s)-1;
FOR(i,0,n) {
if (s[i]!=s[n-i]) {
ke[(long)s[i]].PB((long)s[n-i]);
ke[(long)s[n-i]].PB((long)s[i]);
}
}
FOR(i,0,n)
freq[(long)s[i]]++;
}
long xet[MAXN];
void BFS(long start) {
Q q;
long u=start;
q.push(u); xet[u]=start;
long gtln=u;
while (!q.empty()) {
u=q.front(); q.pop();
FORV(v,ke[u])
if (xet[*v]==0) {
q.push(*v);
xet[*v]=start;
if (freq[*v]>freq[gtln]) gtln=*v;
}
}
FOR(i,1,299)
if (xet[i]==start && i!=gtln) res+=freq[i];
}
void solve() {
FOR(i,1,299)
if (xet[i]==0)
if (!ke[i].empty()) BFS(i);
}
int main() {
inp();
solve();
cout<<res<<endl;
return 0;
}