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

Download