pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串

pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串

ID:14522674

大小:52.00 KB

页数:7页

时间:2018-07-29

pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串_第1页
pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串_第2页
pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串_第3页
pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串_第4页
pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串_第5页
资源描述:

《pku1743 musical theme详细解题报告后缀数组求不重叠的最长重复子串》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、Pku1743MusicalTheme/*Name:pku1743Copyright:ecjtu_acmAuthor:yimaoDate:16/02/1113:35Description:二分答案,后缀数组求不重叠的最长重复子串*/一、题目DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunf

2、ortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequenceofintegersinou

3、rrepresentation.Asubsequenceofamelodyisathemeifit:·isatleastfivenoteslong·appears(potentiallytransposed--seebelow)againsomewhereelseinthepieceofmusic·isdisjointfrom(i.e.,non-overlappingwith)atleastoneofitsotherappearance(s)Transposedmeansthataconstantpositive

4、ornegativevalueisaddedtoeverynotevalueinthethemesubsequence.Givenamelody,computethelength(numberofnotes)ofthelongesttheme.Onesecondtimelimitforthisproblem'ssolutions!InputTheinputcontainsseveraltestcases.ThefirstlineofeachtestcasecontainstheintegerN.Thefollow

5、ingnintegersrepresentthesequenceofnotes.Thelasttestcaseisfollowedbyonezero.OutputForeachtestcase,theoutputfileshouldcontainasinglelinewithasingleintegerthatrepresentsthelengthofthelongesttheme.Iftherearenothemes,output0.SampleInput3025273034394552606979696052

6、45393430262218827874706667646065800SampleOutput5HintUsescanfinsteadofcintoreducethereadtime.SourceLouTiancheng@POJ二、题目大意及分析【前话】我的poj第200题;楼教主男人八题之一;3xian在status里以绝对的时空优势排第一;纪念我的百度空间访问量破2000;我的第一道后缀数组题;典型的二分答案,用后缀数组求不重叠的最长重复子串;网上看题解不下10篇,综合之后才知道他们大概在说些什么,感叹前人栽

7、树,后人乘凉;可以证明本篇文章应该是字数最多的pku1743题解了;【题意】给定一个正整数N(N<=20000),然后是N个整数xi,(1<=xi<=88,1<=i<=N)组成一个有序的整数序列;问这个序列中存在的最长一个符合条件的子序列长度是多少,符合的条件是1、子序列A长度至少为5;2、有另外一个子序列B,且A、B二者没有相交部分(即不存在xi同时在A,B里出现,这里针对下标而言,A,B的元素在整个序列里下标都不一样);3、A,B的长度一样,设x[i],…x[i+k],x[j],…x[j+k],那么要求(x[

8、j]-x[i])=(x[j+1]-x[i+1])=…=(x[i+k],x[j+k]);即按下标对应的元素差值要相等,差值可以是0,1,2,-1,-2……;当然,为了满足2,(i+k)=4;举例说明:例1:135357答案是3,(对应差值是2,如果是35和35对应,则长度是2,求的是存在的最长长度)例2:12341234答案是4,(对

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。