codeforces 159D D. Palindrome pairs( manacher+dp )

题目链接：

codeforces 159D

题目大意：

给出一个字符出，求取这个字符串中互相不覆盖的两个回文子串的对数。

题目分析：

• 首先能够用manacher模板，因为这个算法处理的字符串的长度式奇数，所以我们首先将原字符串拓展，也就是用一个没有出现过的子串填充到每两个字符之间，首位也要添加，这样处理后得到的字符串一定是奇数长度，对于这个字符串，偶数位上的字符对应原字符串中i/2-1位置上的字符。
• 然后就是利用manacher处理出的Len数组解决问题，Len记录的是以当前位置为中心的奇数长度的字符串的回文子串的长度的一半+1。
• 然后我们首先处理出原字符串以每个位置结尾的回文串的个数，然后求取前缀和。
• 然后枚举每个回文串，利用前面求取的前缀和就可以知道右端在当前回文串左端的左侧的回文串的个数。
• 统计枚举的结果就是最终的答案。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 2007

using namespace std;

typedef long long LL;

int temp[MAX<<1];
int Len[MAX<<1];

int init ( char *st , int n )
{
    int i;
    temp[0] = -1;
    for ( int i = 1 ; i <= 2*n ; i+=2 )
    {
        temp[i] = -2;
        temp[i+1] = st[i/2];
    }
    temp[2*n+1] = -2;
    temp[2*n+2] = -3;
    temp[2*n+3] = 0;
    return 2*n+1;
}

void manacher ( int *st , int len )
{
    int mx = 0 , ans = 0 , po = 0;
    for ( int i = 1 ; i <= len ; i++ )
    {
        if ( mx > i )
            Len[i] = min ( mx - i , Len[2*po-i] );
        else 
            Len[i] = 1;
        while ( st[i-Len[i]] == st[i+Len[i]] )
            Len[i]++;
        if ( Len[i]+i > mx )
            mx = Len[i]+i , po = i;
    }
}

char s[MAX];
LL a[MAX<<1],ans;

int main ( )
{
    while ( ~scanf ( "%s" , s ) )
    {
        ans = 0;
        memset ( a , 0 , sizeof ( a ) );
        int n = strlen ( s );
        manacher ( temp , init ( s, n ) );
        for ( int i = 1 ; i <= 2*n ; i++ )
        {
            int x = Len[i];
            if ( i&1 ) 
                for ( int j = 1 ; j < x ; j += 2 ) 
                    a[i+j]++;
            else
                for ( int j = 0 ; j < x ; j += 2 )
                    a[i+j]++;
        }
        a[0] = 0;
        for ( int i = 1 ; i <= 2*n ; i++ )
            a[i] += a[i-1];
        for ( int i = 1 ; i <= 2*n ; i++ )
        {
            int x = Len[i];
            if ( i&1 )
                for ( int j = 1 ; j < x ; j += 2 )
                    ans += a[i-j-1];
            else 
                for ( int j = 0 ; j < x ; j += 2 )
                    ans += a[i-j-1];
        }
        printf ( "%lld\n" , ans );
    }
}