列表

详情

NC14300. Palindrome

描述

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  S[1..3n−2](n≥2) is one-and-half palindromic if and only if it satisfies  S[i]=S[2n−i]=S[2n+i−2](1≤i≤n) .For example,  abcbabc  is one-and-half palindromic string, and  abccbaabc  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.

输入描述

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 500000), this string only consists of lowercase letters.

输出描述

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

示例1

输入: 

1
ababcbabccbaabc

输出: 

2

说明:

In the example input, there are two substrings which are one-and-half palindromic strings, abab and abcbabc.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 309ms, 内存消耗: 10560K, 提交时间: 2022-09-29 21:14:04 

#include<cstdio>
#include<cstring>
#define ri register int
#define ll long long
#define maxn 500005
#define fo(i,x,y) for(ri i(x);i<=y;++i)
#define fd(i,x,y) for(ri i(x);i>=y;--i)
using namespace std;
struct node{
	int l,r,pos;
}a[maxn];
int T,n,d[maxn],c[maxn];
ll ans;
char s[maxn];
inline ll min(ll x,ll y){
	return x<y?x:y;
}
inline int lowbit(ri x){
	return x&(~x+1);
}
inline void update(ri x){
	for(;x<=n;x+=lowbit(x))++c[x];
}
inline int query(ri x){
	ri res(0);for(;x;x-=lowbit(x))res+=c[x];
	return res;
}
inline void swap(node &x,node &y){
	node t=x;x=y;y=t;
}
inline void qsort(ri l,ri r){
	ri i=l,j=r,mid=a[l+r>>1].l;
	while(i<=j){
		while(a[i].l<mid)++i;while(a[j].l>mid)--j;
		if(i<=j){
			swap(a[i],a[j]);++i;--j;
		}
	}
	if(l<j)qsort(l,j);if(i<r)qsort(i,r);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);n=strlen(s+1);
		ri l(0),r(0);
		fo(i,1,n)d[i]=0;
		fo(i,1,n){
			if(i<=r){
				ri j=l+r-i;d[i]=min(r-i+1,d[j]);
				if(d[j]<r-i+1)continue;
			}
			while(i-d[i]>=1&&i+d[i]<=n&&s[i-d[i]]==s[i+d[i]])++d[i];
			if(i+d[i]-1>r)l=i-d[i]+1,r=i+d[i]-1;
		}
		//fo(i,1,n)printf("%d %d\n",i,d[i]);
		fo(i,1,n)a[i].l=i-d[i]+1;fo(i,1,n)a[i].r=i+d[i]-1;fo(i,1,n)a[i].pos=i;
		fo(i,0,n)c[i]=0;qsort(1,n);ri now(1);ans=0;
		fo(i,1,n){
			while(now<=n&&a[now].l<=i)update(a[now++].pos);
			ans+=query(i+d[i]-1)-i;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 400ms, 内存消耗: 13616K, 提交时间: 2019-04-16 14:48:20 

#include<bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ll long long
const int MAXN=5e5+5;
char Ma[MAXN];
int Mp[MAXN];
void Manacher(char s[],int len){
//因为只需要求奇数长度的回文串，所以除了起始字符外不用添加特殊字符 
	int l=len+1;
	Ma[0]='$';
	Ma[l]=0;
	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;
		}
	}
}
int t;
int c[MAXN];
int lowbit(int x){
	return x&(-x);
}
void add(int x,int z=1){
	while(x<MAXN){
		c[x]+=z;
		x+=lowbit(x);
	}
}
int query(int x){
	int res=0;
	while(x>0){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
struct node{
	int d,pos; 
	bool operator<(const node &p)const{//按差值排序 
		return d<p.d;
	}
}a[MAXN];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%s",Ma+1);
		int len=strlen(Ma+1);
		Manacher(Ma,len);
		mst(c,0);
		for(int i=1;i<=len;i++){ 
			Mp[i]--;
		}
		ll  ans=0;
		int cnt=0;
		for(int i=len;i>=1;i--){ 
			a[cnt].d=i-Mp[i];
			a[cnt].pos=i;
			cnt++;
		}
		sort(a,a+cnt);
		for(int i=1,j=0;i<len;i++){
			while(j<cnt&&a[j].d<=i){
				add(a[j].pos);
				j++;
			}
			ans+=query(i+Mp[i])-query(i);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 685ms, 内存消耗: 13496K, 提交时间: 2017-11-13 22:34:28 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 500005
#define maxm 1000005
struct node
{
	int x,l;
}q[maxm];
char s[maxm];
int len[maxm],c[maxm];
void Manacher(char *s)
{
	s[0]='#';
	int num=strlen(s+1);
	int mx=0,id=0;
	for(int i=1;i<=num;i++)
	{
		if(mx>i)
			len[i]=min(mx-i,len[2*id-i]);
		else
			len[i]=1;
		while(s[i-len[i]]==s[i+len[i]])
			len[i]++;
		if(len[i]+i>mx)
			mx=len[i]+i,id=i;
	}
}
bool comp(node a,node b)
{
	return a.l>b.l;
}
void add(int x,int n)
{
	while(x<=n)
		c[x]++,x+=x&(-x);
}
int findsum(int x)
{
	int res=0;
	while(x)
		res+=c[x],x-=x&(-x);
	return res;
}
int main(void)
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s+1);
		Manacher(s);
		int num=strlen(s+1);
		for(int i=0;i<=num;i++)
			c[i]=0;
		for(int i=1;i<=num;i++)
		{
			q[i].x=i;
			q[i].l=i+len[i]-1;
		}
		sort(q+1,q+num+1,comp);
		int p=1;ll ans=0;
		for(int i=num;i>0;i--)
		{
			while(p<=num && q[p].l>=i)
				add(q[p++].x,num);
			ans+=findsum(i-1)-findsum(i-len[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com