【Manacher】Colorful String

The value of a string s is equal to the number of different letters which appear in this string.

Your task is to calculate the total value of all the palindrome substring.

Input

The input consists of a single string |s|(≤∣s∣≤×^ ).

The string s only contains lowercase letters.

Output

Output an integer that denotes the answer.

样例输入

abac

样例输出 

样例解释

abac has palindrome substrings a,b,a,c,abaa,b,a,c,aba，ans the total value is equal to ++++=。

【题解】

　　Manacher，先预处理一波，然后找出每一个位置的26个字母下一个位置，存在一个vector里面，然后最后找的时候就是差值 × 对应的个数。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=3e5+;

 char S[N],T[N<<];

 int Len[N*];

 int nxt[N][];

 vector<int>V[N];

 void Manacher(char *s){

     int L=strlen(s);

     int po =  , mx= ;

     for(int i=;i<=L*;i++){

         T[i] = i&? '#' : s[i/-] ;

     }

     T[] = '@';

     T[*L+] = '#';

     T[*L+] = '\0';

     ll tmp =  ;

     for(int i=;i<=*L;i++){

         if( i<mx ){

             Len[i]=min( mx-i , Len[*po-i] );

         }else{

             Len[i] =  ;

         }

         while( T[i+Len[i]]==T[i-Len[i]] ){

             Len[i]++;

         }

         if( i + Len[i] > mx ){

             po = i;

             mx = i + Len[i];

         }

     }

 }

 int main()

 {

     scanf("%s",S);

     Manacher(S);

     int len1 = strlen( S ) ;

     int len2 = strlen( T ) ;

     for( int j =  ; j <  ; j++ ){

         int pos = INT_MAX ;

         for( int i = len1 -  ; i >=  ; i-- ){

             if( S[i] == j + 'a' ) pos = i ;

             nxt[i][j] = pos ;

         }

     }

     for( int i =  ; i < len1 ; i++ ){

         for( int j =  ; j <  ; j++ ){

             V[i].push_back( nxt[i][j] ) ;

         }

         sort( V[i].begin() , V[i].end() );

     }

     /*

     for( int i = 1 ; i < len2 ; i++ ){

         printf("%d : %c , Len %d \n",i , T[i] , Len[i] );

     }

     */

     ll ans =  ;

     for( int i =  ; i < len2 ; i++ ){

         int L = Len[i] /  ;

         if( L ==  ) continue ;

         int Id = i /  -  ;

         if( i &  ) Id ++ ;

         int RR = Id + L -  ;

         int Last = V[Id][] ;

         int cnt =   ;

         for( auto x : V[Id] ){

             if( x > RR ) break ;

             int r = x -  ;

             ans = ans + (ll)( cnt ++ ) * (ll) ( r - Last +  );

             Last = x ;

         }

         if( RR >= Last ){

             ans = ans + (ll) cnt * (ll) ( RR - Last +  );

         }

     }

     printf("%lld\n",ans);

     return ;

 }

 //jswbutgecnmqnuagqnvxfljfffzvudcfvygpro

巴特西

【Manacher】Colorful String

最新文章

热门文章