下一页 »Current position : 首页 >> 后缀数组
PKU2019数据结构与算法实习作业 11~21
题目来源：http://dapractise.openjudge.cn/2019hwall/多模式串字符串匹配模板题AC自动机模板题[crayon-676cb68238849819981794/]POJ3987ComputerVirusonPlanetPandora[crayon-676cb68238859077146756/]躲不开的病毒找自动机上的环[crayon-676cb68238863598427007/]POJ3691DNArepairDP，考虑前i个字符且停留在trie树上编号为j的节点时，字符串所修改的最小次数[crayon-676cb68238874799571209/]POJ3450Corpor...
PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-676cb68239e82189772126/]POJ1860CurrencyExchange最短路模板[crayon-676cb68239e8d300796189/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-676cb6823a502962281758/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-676cb6823a50c546298164/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-676cb6823a512680101070/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-6...
「BZOJ3230」相似子串
DescriptionInput输入第1行，包含3个整数N，Q。Q代表询问组数。第2行是字符串S。接下来Q行，每行两个整数i和j。（1≤i≤j）。Output输出共Q行，每行一个数表示每组询问的答案。如果不存在第i个子串或第j个子串，则输出-1。SampleInput53ababa3559810SampleOutput1816-1HINT样例解释第1组询问：两个子串是“aba”,“ababa”。f=32+32=18。第2组询问：两个子串是“ababa”,“baba”。f=02+42=16。第3组询问：不存在...
「POJ1743」Musical Theme
DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...
[sdoi2008] Sandy的卡片
![[sdoi2008] Sandy的卡片](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_12-30-38.jpg)
时限0.5sSandy和Sue的热衷于收集干脆面中的卡片。然而，Sue收集卡片是因为卡片上漂亮的人物形象，而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记，第i张卡片的序列长度为Mi，要想兑换人物模型，首先必须要集够N张卡片，对于这N张卡片，如果他们都有一个相同的子串长度为k，则可以兑换一个等级为k的人物模型。相同的定义为：两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。S...
「BZOJ3238」[Ahoi2013] 差异
![「BZOJ3238」[Ahoi2013] 差异](http://www.lydsy.com/JudgeOnline/upload/201306/1(4).jpg)
DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了，这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...
「uoj35」后缀排序
这是一道模板题。读入一个长度为n的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为1到n。除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出n−1个整数分别表示排序后相邻后缀的最长公共前缀的长度。输入格式一行一个长度为n的仅包含小写英文字母的字符串。输出格式第一行n个整数，第i个整数表示排名为i的后缀的第一个字符...
「CODEVS3160」最长公共子串
题目描述Description给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。输入描述InputDescription读入两个字符串输出描述OutputDescription输出最长公共子串的长度样例输入SampleInput[crayon-676cb6823d4bc916387365/]样例输出SampleOutput27数据范围及提示DataSize&Hint单个字符串的长度不超过100000题解算法1：后缀数组同poj2774bzoj挂了没事干。。。2014.9.21*12015.2.6*1[crayon-676cb6823d4c437...
「POJ3693」Maximum repetition substring
DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumberRsuchthatthestringcanbepartitionedintoRsameconsecutivesubstrings.Forexample,therepetitionnumberof"ababab"is3and"ababa"is1.Givenastringcontaininglowercaseletters,youaretofindasubstringofitwithmaximumrepetitionnumber.InputTheinputconsistsofmultipletestcases.Eachtestcasecontainsexactlyoneline,whichgivesanon-emptystringconsisti...
「hdu3518」Boring counting
ProblemDescription035nowfacedatoughproblem,hisenglishteachergiveshimastring,whichconsistswithnlowercaseletter,hemustfigureouthowmanysubstringsappearatleasttwice,moreover,suchapearancescannotoverlapeachother.Takeaaaaasanexample.”a”apearsfourtimes,”aa”apearstwotimeswithoutoverlaping.however,aaacan’tapearmorethanonetimewithoutoverlaping.sincewecanget“aaa”from[0-2](Thepositionofstringbegins...
「POJ2774」Long Long Message
DescriptionThelittlecatismajoringinphysicsinthecapitalofByterland.Apieceofsadnewscomestohimthesedays:hismotherisgettingill.Beingworriedaboutspendingsomuchonrailwaytickets(Byterlandissuchabigcountry,andhehastospend16shoursontraintohishometown),hedecidedonlytosendSMSwithhismother.Thelittlecatlivesinanunrichfamily,sohefrequentlycomestothemobileservicecenter,tocheckhowmuchmoneyhehasspentonS...
OI 课件=>
近期评论