ccpc哈尔滨A [HDU-6230] Palindrome Manacher+树状数组

提交链接

Alice like strings, especially long strings. For each string, she has a special evaluation system to judge how elegant the string is. She defines that a string S1..3n−2S1..3n−2 is one-and-half palindromic if and only if it satisfies S[i]=S[2n−i]=S2n+i−2S[i]=S[2n−i]=S2n+i−2.For example, abcbabcabcbabc is one-and-half palindromic string, and abccbaabcabccbaabc is not. Now, Alice has generated some long strings. She ask for your help to find how many substrings which is one-and-half palindromic.

Input
The first line is the number of test cases. For each test case, there is only one line containing a string(the length of strings is less than or equal to 500000500000), this string only consists of lowercase letters.

Output
For each test case, output a integer donating the number of one-and-half palindromic substrings.

Sample Input
1
ababcbabccbaabc

Sample Output
2

Hint
In the example input, there are two substrings which are one-and-half palindromic strings, <nobr> abab </nobr> and <nobr> abcbabc </nobr>.

题意：给定一个字符串，统计有多少个子串是one−and−half palindromic. (即字符串长度为3n−2,且满足S[i]=S[2n−i]=S[2n+i]
题意：问题目描述的字串有多少个？

思路：
+ 可以发现这种字符串是关于S[n]和S[2n-1]对称的，所以枚举S[2n-1]，看在S[2n-1]的半径范围内有多少个S[n]的半径范围包括S[2n-1]，可以manacher找到半径，然后树状数组求答案;
+
对one−and−half palindromic字符串稍作分析：可以发现，
这种字符串的形式是这样的：$L(S)@R(S)$L(S)@ $、@
分别表示某一个小写字母。 L(S)、R(S)分别表示某一个字符串，和该字符串的逆串（可为空串）。
首先，用Manacher预处理出每个字符为中心的最长回文串长度,p[i]。 设子串中第二个@,第二个$ 在原串中的下标分别为i,j.
那么，该子串必然要满足：j−p[j]+1≤i

//此题主要是利用了树状数组或线段树来表达每个回文串中心点
//的影响，通过依次加1的方式，这样如果当前位置不是回文串
//圆心，那么他只能影响到当前位置，因为在下一个位置就被删除了
//具体可见out2，这是一个混乱串的位置
//
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6;
char Ma[maxn];
int Mp[maxn];
void Manacher(char s[],int len)
{
    int l = 0;
    Ma[l++] = '$';
    Ma[l++]='#';
    for(int i=0;i<len;i++)
    {
        Ma[l++] = s[i];
        Ma[l++] = '#';
    }
    Ma[l]=0;
   // printf("%s\n",Ma); //增加#后，字符串从1开始，不带开头的$号，字符串长度为奇数
  int mx = 0,id = 0;
   for(int i=0;i<l;i++)
   {
       Mp[i] = mx>i?min(Mp[2*id-i],mx-i):1;
       while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
        Mp[i]++;
        if(i+Mp[i]>mx)
       {
           mx = i+Mp[i];
           id = i;
       }
   }
}
vector<int>v[maxn];
char s[maxn];
int c[maxn];
int len;
int lowbit(int x)
{
    return x&-x;
}
void add(int pos,int val)
{
    pos++;
    for(int i=pos;i<=len;i+=lowbit(i))
        c[i]+=val;
}
int getsum(int pos)
{
    pos++;
    int ret = 0;
    for(int i=pos;i>0;i-=lowbit(i))
    {
        ret+=c[i];
    }
    return ret;
}
int main()
{
    //freopen("out.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        len = strlen(s);
        Manacher(s,len);
// for(int i=0;i<len;i++)
// {
// printf("%d ",Mp[i]);
// }
// cout<<endl;
// 这是增加了#后得到的答案数组
        for(int i=0;i<len;i++)
        {
            Mp[i] = Mp[i*2+2]/2;
        }
// 这步是去掉#后得到的原字符串的答案数组
// for(int i=0;i<len;i++)
// {
// printf("%d ",Mp[i]);
// }
// cout<<endl; //打印出来看
        for(int i=0;i<len;i++)
           v[i].clear();
           for(int i=0;i<len;i++)
            c[i] = 0;
           long long ans = 0;
           for(int i=0;i<len;i++)
           {
               for(int pos:v[i])
                add(pos,-1);//这一步是用来消除影响的
               int st = i-Mp[i]+1;//计算字符的影响范围的左端点，避免重复计算
// cout<<"i:"<<i<<" st:"<<st<<endl;
// cout<<getsum(i-1)<<" "<<getsum(st-1)<<endl;
               ans+=getsum(i-1)-getsum(st-1);
               //注意前缀和的用法，左区间端点减1
               //这里虽然是i位置加的ans，但是表示的确是ans-1出存在一个串心（类比圆心）
               add(i,1);//这个是基础，用来表示每个位置的影响
// cout<<i+Mp[i]<<endl;
// cout<<endl;
               v[i+Mp[i]].push_back(i);//通过这一步，延迟那些有回文串的
               //串心的影响范围

// for(int i=0;i<len;i++)
// printf("%d ",getsum(i)); //打印前缀和
// cout<<endl;
           }
// for(int i=0;i<len;i++)
// {
// int uu = v[i].size();
// cout<<"i"<<i<<" ";
// for(int j=0;j<uu;j++)
// {
// printf("%d ",v[i][j]);
// }
// cout<<endl;
// }
           printf("%lld\n",ans);
    }
    return 0;
}

下面是两组测试数据

out1

$#a#b#a#b#c#b#a#b#c#c#b#a#a#b#c#
1 1 2 1 4 1 4 1 2 1 8 1 2 1 6 
1 2 2 1 4 1 3 1 1 1 1 1 1 1 1 
i:0 st:0
0 0
1

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
i:1 st:0
0 0
3

0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
i:2 st:1
1 0
4

0  1  2  2  2  2  2  2  2  2  2  2  2  2  2  
i:3 st:3
1 1
4

0  0  1  2  2  2  2  2  2  2  2  2  2  2  2  
i:4 st:1
0 0
8

0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  
i:5 st:5
1 1
6

0  0  0  0  1  2  2  2  2  2  2  2  2  2  2  
i:6 st:4
1 0
9

0  0  0  0  1  1  2  2  2  2  2  2  2  2  2  
i:7 st:7
2 2
8

0  0  0  0  1  1  2  3  3  3  3  3  3  3  3  
i:8 st:8
1 1
9

0  0  0  0  0  0  1  1  2  2  2  2  2  2  2  
i:9 st:9
0 0
10

0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  
i:10 st:10
0 0
11

0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  
i:11 st:11
0 0
12

0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  
i:12 st:12
0 0
13

0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  
i:13 st:13
0 0
14

0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  
i:14 st:14
0 0
15

0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  
i0 
i1 0 
i2 
i3 1 
i4 2 3 
i5 
i6 5 
i7 
i8 4 7 
i9 6 8 
i10 9 
i11 10 
i12 11 
i13 12 
i14 13 
2

out2

$#a#s#d#u#i#o#q#w#s#h#p#q#o#i#k#
1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
i:0 st:0
0 0
1

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
i:1 st:1
0 0
2

0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  
i:2 st:2
0 0
3

0  0  1  1  1  1  1  1  1  1  1  1  1  1  1  
i:3 st:3
0 0
4

0  0  0  1  1  1  1  1  1  1  1  1  1  1  1  
i:4 st:4
0 0
5

0  0  0  0  1  1  1  1  1  1  1  1  1  1  1  
i:5 st:5
0 0
6

0  0  0  0  0  1  1  1  1  1  1  1  1  1  1  
i:6 st:6
0 0
7

0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  
i:7 st:7
0 0
8

0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  
i:8 st:8
0 0
9

0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  
i:9 st:9
0 0
10

0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  
i:10 st:10
0 0
11

0  0  0  0  0  0  0  0  0  0  1  1  1  1  1  
i:11 st:11
0 0
12

0  0  0  0  0  0  0  0  0  0  0  1  1  1  1  
i:12 st:12
0 0
13

0  0  0  0  0  0  0  0  0  0  0  0  1  1  1  
i:13 st:13
0 0
14

0  0  0  0  0  0  0  0  0  0  0  0  0  1  1  
i:14 st:14
0 0
15

0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  
i0 
i1 0 
i2 1 
i3 2 
i4 3 
i5 4 
i6 5 
i7 6 
i8 7 
i9 8 
i10 9 
i11 10 
i12 11 
i13 12 
i14 13 
0