2015 UESTC 搜索专题M题 Palindromic String 马拉车算法
Palindromic String
Time Limit: 20 Sec Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/contest/show/61Description
秋实大哥喜欢探索新鲜事物,最近他发明了一种新型回文串,叫K重回文串!今天他想用它来考考小朋友们。
秋实大哥给出了与K重回文串有关的信息
任何字符串都属于0重回文串,包括空字符串。
一个长度为N的字符串S,S是K(k≥1)重回文串,当且仅当S是回文串,且其长度为⌊N2⌋的前缀和长度为⌊N2⌋的后缀是K−1重回文串。
如果一个字符串是K重回文串,则称该字符串有一个回文值为K。一个字符串可以有多个回文值,比如S=abaaba,其回文值可为0,1,2,3。
字符串的最大回文值是该字符串所有回文值的最大值。
若字符串S的最大回文值≥1,则S一定是回文串。
一个字符串S,如果其正着读和反着读是一样的,则称S是回文串,比如aabaa,aba,a。但abc,abab,aacba就不是回文串。
一个长度为N的字符串S,其有N+1个前缀和N+1个后缀(不一定非空),比如abcde,有6个前缀,分别是空字符串,a,ab,abc,abcd,abcde;有6个后缀,分别是空字符串,e,de,cde,bcde,abcde。
秋实大哥给你一个字符串S,他想问问你,S所有前缀的最大回文A的某一段完全重合,或者能够经过上下左右平移与折线A的某一段完全重合,则表示秋实大哥吹出了妹子的一部分旋律。
Input
Output
输出一个整数,表示S所有前缀的最大回文值之和。
Sample Input
Sample Output
HINT
题意
题解:
首先跑一发马拉车算法,然后得到所有字符的P数组,表示回文串的长度
然后我们再递归求解
然后就可以知道每一个回文串是几重
(虽然我觉得复杂度可能会很高,但是跑的很快,不知道为什么……
代码:
//qscqesze #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define maxn 2000010 #define mod 10007 #define eps 1e-9 int Num; char CH[20]; //const int inf=0x7fffffff; //нчоч╢С const int inf=0x3f3f3f3f; /* inline void P(int x) { Num=0;if(!x){putchar(‘0‘);puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts(""); } */ inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } inline void P(int x) { Num=0;if(!x){putchar(‘0‘);puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts(""); } //************************************************************************************** char s[maxn]; char str[maxn*2]; int l; int p[maxn*2]; int manacher(char s[],int l) { int i,j,k,ans=0; for(i=1;i<=l;++i)str[i<<1]=s[i],str[(i<<1)+1]=‘#‘; str[1]=‘#‘;str[l*2+1]=‘#‘;str[0]=‘&‘;str[l*2+2]=‘$‘; l=l*2+1;j=0; for(i=1;i<=l;) { while(str[i-j-1]==str[i+j+1])++j; p[i]=j;if(j>ans)ans=j; for(k=1;k<=j&&p[i]-k!=p[i-k];++k)p[i+k]=min(p[i-k],p[i]-k); i+=k;j=max(j-k,0); } return ans; } int main() { scanf("%s",s+1); l=strlen(s+1); manacher(s,l); l=l*2+1; int ans=0; for(int i=2;i<=(l+1)/2;i++) { int tmp=p[i]; int pos=i; while(tmp+1>=pos&&tmp!=0) { ans++; pos=(pos+1)/2; tmp=p[pos]; } //cout<<ans<<endl; } cout<<ans<<endl; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。