• 【bzoj3998】[TJOI2015]弦论

    【bzoj3998】[TJOI2015]弦论

    Description对于一个给定长度为N的字符串,求它的第K小子串是什么。Input 第一行是一个仅由小写英文字母构成的字符串S第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。Output输出仅一行,为一个数字串,为第K小的子串。如果子串数目不足K个,则输出-1SampleInputaabc03SampleOutputaabHINT N<=5*10^5T<2K<=10^9题解日常o...

    52015年4月22日2,317后缀自动机
  • 【bzoj2946】[Poi2000]公共串

    【bzoj2946】[Poi2000]公共串

    Description      给出几个由小写字母构成的单词,求它们最长的公共子串的长度。任务:l       读入单词l       计算最长公共子串的长度l       输出结果Input文件的第一行是整数n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。Output仅一行,一个整数,最长公共子串的长度。SampleInput3abcbbcaacbcSampleOutput2题解后缀自动机...

    12015年4月21日1,701后缀自动机
  • 【poj1743】Musical Theme

    【poj1743】Musical Theme

    DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...

    22015年4月20日2,221后缀数组,后缀自动机
  • UOJ Easy Round #1

    UOJ Easy Round #1

    http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。【UER#1】猜数[crayon-58d3662fa0c93547843104/]【UER#1】跳蚤OS[crayon-58d3662fa0ca1914987467/]【UER#1】DZYLovesGraph[crayon-58d3662fa0cac983513182/] ...

    02015年4月13日2,098并查集,AC自动机
  • [sdoi2008]Sandy的卡片

    [sdoi2008]Sandy的卡片

    时限0.5sSandy和Sue的热衷于收集干脆面中的卡片。然而,Sue收集卡片是因为卡片上漂亮的人物形象,而Sandy则是为了积攒卡片兑换超炫的人物模型。每一张卡片都由一些数字进行标记,第i张卡片的序列长度为Mi,要想兑换人物模型,首先必须要集够N张卡片,对于这N张卡片,如果他们都有一个相同的子串长度为k,则可以兑换一个等级为k的人物模型。相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。S...

    72015年4月10日1,767KMP,后缀数组
  • 【bzoj3238】[Ahoi2013]差异

    【bzoj3238】[Ahoi2013]差异

    DescriptionInput一行,一个字符串SOutput一行,一个整数,表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧,bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了,这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值,这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...

    62015年4月9日2,180后缀数组,单调栈
  • 【uoj35】后缀排序

    【uoj35】后缀排序

    这是一道模板题。读入一个长度为n的由小写英文字母组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为1到n。除此之外为了进一步证明你确实有给后缀排序的超能力,请另外输出n−1个整数分别表示排序后相邻后缀的最长公共前缀的长度。输入格式一行一个长度为n的仅包含小写英文字母的字符串。输出格式第一行n个整数,第i个整数表示排名为i的后缀的第一个字符...

    22015年4月9日1,399后缀数组
  • NOI2014动物园

    NOI2014动物园

    Description近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。某天,园长给动物们讲解KMP算法。园长:“对于一个字符串S,它的长度为L。我们可以在O(L)的时间内,求出一个名为next的数组。有谁预习了next数组的含义吗?”熊猫:“对于字符串S的前i个字符构成的子串,既是它的后...

    152015年2月8日1,922KMP
  • 【codevs3160】最长公共子串

    【codevs3160】最长公共子串

    题目描述Description给出两个由小写字母组成的字符串,求它们的最长公共子串的长度。输入描述InputDescription读入两个字符串输出描述OutputDescription输出最长公共子串的长度样例输入SampleInput[crayon-58d3662fb266d933334547/]样例输出SampleOutput27数据范围及提示DataSize&Hint单个字符串的长度不超过100000题解算法1:后缀数组同poj2774bzoj挂了没事干。。。2014.9.21*12015.2.6*1[crayon-58d3662fb267b49...

    62015年2月6日2,504后缀数组,后缀自动机
  • 【fjwc2015】Galaxy

    【fjwc2015】Galaxy

    【题目描述】小X进入了平行宇宙,想在某个平行宇宙开始一段生活。平行宇宙之间用长度为N的仅含有A、B、C、D四个字母的序列标识。每一个由A,B,C,D组成的长度为N的序列标识着不同的平行宇宙。有趣的是,不同的宇宙对应着小X的不同人生,在某些宇宙中,小X的人生过得并不愉快。小X得到了M个特征碎片,特征碎片都为长度小于10的由A,B,C,D构成的序列。如果某个平行宇宙的标识序列包含某个特征碎片(即特征碎片为宇宙...

    02015年2月3日1,291AC自动机,矩阵乘法
  • 【bzoj2754】[SCOI2012]喵星球上的点名

    【bzoj2754】[SCOI2012]喵星球上的点名

    Descriptiona180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。然而,由于喵星人的字码过于古怪,以至于不能用ASCII码来表示。为了方便描述,a180285决定用数串来表示喵星人的名字。现在你能帮助a1...

    52015年1月15日2,810STL,AC自动机
  • 【poj3693】Maximum repetition substring

    【poj3693】Maximum repetition substring

    DescriptionTherepetitionnumberofastringisdefinedasthemaximumnumberRsuchthatthestringcanbepartitionedintoRsameconsecutivesubstrings.Forexample,therepetitionnumberof"ababab"is3and"ababa"is1.Givenastringcontaininglowercaseletters,youaretofindasubstringofitwithmaximumrepetitionnumber.InputTheinputconsistsofmultipletestcases.Eachtestcasecontainsexactlyoneline,whichgivesanon-emptystringconsisti...

    32015年1月14日1,664ST表,后缀数组
  • 【hdu3518】Boring counting

    【hdu3518】Boring counting

    ProblemDescription035nowfacedatoughproblem,hisenglishteachergiveshimastring,whichconsistswithnlowercaseletter,hemustfigureouthowmanysubstringsappearatleasttwice,moreover,suchapearancescannotoverlapeachother.Takeaaaaasanexample.”a”apearsfourtimes,”aa”apearstwotimeswithoutoverlaping.however,aaacan’tapearmorethanonetimewithoutoverlaping.sincewecanget“aaa”from[0-2](Thepositionofstringbegins...

    02015年1月13日1,020后缀数组