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