首页 > 代码库 > hdu 4763 Theme Section
hdu 4763 Theme Section
Theme Section
http://acm.hdu.edu.cn/showproblem.php?pid=4763
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
It‘s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a ‘theme section‘. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of ‘EAEBE‘, where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters ‘a‘ - ‘z‘.
To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?
To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?
Input
The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.
Output
There will be N lines in the output, where the i-th line denotes the maximum possible length of the theme section of the i-th song.
Sample Input
5
xy
abc
aaa
aaaaba
aaxoaaaaa
Sample Output
0
0
1
1
2
Source
2013 ACM/ICPC Asia Regional Changchun Online
Recommend
liuyiding | We have carefully selected several similar problems for you: 6032 6031 6030 6029 6028
题意:求字符串中满足 EAEBE 最长的E
(A与B可以相同,也可以没有)
扩展kmp求出next数组
满足第一个E和最后一个E的条件是 nxt[i]=len-nxt[i]
再在nxt[i]——i-nxt[i]范围内查找最大的nxt[],如果>=nxt[i],那么当前的nxt[i]就是合法的
查找区间最大值我用的线段树
#include<cstdio>#include<cstring>#include<algorithm>#define N 1000011using namespace std;char s[N];int len,nxt[N];struct node{ int l,r,maxn;}tr[N*4];void getnxt(){ int a=0; nxt[0]=len; while(a+1<len && s[a]==s[a+1]) a++; nxt[1]=a; int p,l,j; a=1; for(int k=2;k<len;k++) { p=a+nxt[a]-1; l=nxt[k-a]; if(k-1+l>=p) { j=p-k+1>0 ? p-k+1 : 0; while(k+j<len && s[k+j]==s[j]) j++; nxt[k]=j; a=k; } else nxt[k]=l; }}void build(int k,int l,int r){ tr[k].l=l; tr[k].r=r; if(l==r) { tr[k].maxn=nxt[l]; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);}int query(int k,int opl,int opr){ if(tr[k].l>=opl && tr[k].r<=opr) return tr[k].maxn; int mid=tr[k].l+tr[k].r>>1; int p=0,q=0; if(opl<=mid) p=query(k<<1,opl,opr); if(opr>mid) q=query(k<<1|1,opl,opr); return max(p,q); }int main(){ int n,ans; scanf("%d",&n); while(n--) { scanf("%s",s); len=strlen(s); getnxt(); build(1,0,len); ans=0; for(int i=2;i<len;i++) { if(nxt[i]!=len-i) continue; if(i-nxt[i]<nxt[i]) continue; if(query(1,nxt[i],i-nxt[i])>=nxt[i]) { ans=nxt[i]; break; } } printf("%d\n",ans); }}
hdu 4763 Theme Section
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。