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

Download