后缀自动机 - hzwer.com

「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-6767e392b0f90558953498/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-6767e392b0f9e041936140/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-6767e392b...
02015年6月15日7,559深度搜索,广度搜索,后缀自动机,概率与期望,莫比乌斯反演

「BZOJ3926」[ZJOI2015] 诸神眷顾的幻想乡
陈老师语文水平高超陈老师的博客：http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/[crayon-6767e392b29b3738165874/]
02015年5月1日7,275深度搜索,后缀自动机
「BZOJ3676」[Apio2014] 回文串
Description考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。Input输入只有一行，为一个只包含小写字母(a-z)的非空字符串s。Output输出一个整数，为逝查回文子串的最大出现值。SampleInput「样例输入l」abacaba「样例输入2]wwwSampleOutput「样例输出l」7「样例输出2]4HINT一个串是回文的，当且仅当它从左到右读和从右到...
182015年4月23日11,200后缀自动机,manacher
「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...
62015年4月22日7,202后缀自动机
「BZOJ2946」[POI2000] 公共串
Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：l 读入单词l 计算最长公共子串的长度l 输出结果Input文件的第一行是整数n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。Output仅一行，一个整数，最长公共子串的长度。SampleInput3abcbbcaacbcSampleOutput２题解后缀自动机...
12015年4月21日5,380后缀自动机
「POJ1743」Musical Theme
DescriptionAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresentationofmelodiesignoresthenotionofmusicaltiming;but,thisprogrammingtaskisaboutnotesandnottimings.Manycomposersstructuretheirmusicaroundarepeating&qout;theme&qout;,which,beingasubsequenceofanentiremelody,isasequ...
12015年4月20日6,353后缀数组,后缀自动机
「CODEVS3160」最长公共子串
题目描述Description给出两个由小写字母组成的字符串，求它们的最长公共子串的长度。输入描述InputDescription读入两个字符串输出描述OutputDescription输出最长公共子串的长度样例输入SampleInput[crayon-6767e392b6ca6594498506/]样例输出SampleOutput27数据范围及提示DataSize&Hint单个字符串的长度不超过100000题解算法1：后缀数组同poj2774bzoj挂了没事干。。。2014.9.21*12015.2.6*1[crayon-6767e392b6cb140...
62015年2月6日7,496后缀数组,后缀自动机
「BZOJ2555」SubString
Description懒得写背景了，给你一个字符串init，要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)你必须在线支持这些操作。Input 第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init接下来Q行，每行2个字符串Type,StrType是ADD的话表示在后面插入字符串。Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。为了体现在...
02014年9月25日8,848后缀自动机,link cut tree
「SPOJ7258」Lexicographical Substring Search
LittleDaniellovestoplaywithstrings!Healwaysfindsdifferentwaystohavefunwithstrings!Knowingthat,hisfriendKinandecidedtotesthisskillssohegavehimastringSandaskedhimQquestionsoftheform:IfalldistinctsubstringsofstringSweresortedlexicographically,whichonewillbetheK-thsmallest?AfterknowingthehugenumberofquestionsKinanwillask,Danielfiguredoutthathecan'tdothisalone.Daniel,ofcourse,knowsyourexc...
02014年9月23日4,781后缀自动机
「SPOJ1812」Longest Common Substring II
Astringisfinitesequenceofcharactersoveranon-emptyfinitesetΣ.Inthisproblem,Σisthesetoflowercaseletters.Substring,alsocalledfactor,isaconsecutivesequenceofcharactersoccurrencesatleastonceinastring.Nowyourtaskisabitharder,forsomegivenstrings,findthelengthofthelongestcommonsubstringofthem.Herecommonsubstringmeansasubstringoftwoormorestrings.InputTheinputcontainsatmost10lines,eachlineconsistso...
02014年9月22日4,302后缀自动机
「SPOJ8222」Substrings
YouaregivenastringSwhichconsistsof250000lowercaselatinlettersatmost.WedefineF(x)asthemaximalnumberoftimesthatsomestringwithlengthxappearsinS.Forexampleforstring'ababa'F(3)willbe2becausethereisastring'aba'thatoccurstwice.YourtaskistooutputF(i)foreveryisothat1<=i<=|S|.InputStringSconsistsofatmost250000lowercaselatinletters.OutputOutput|S|lines.Onthei-thlineoutputF(i).Example...
72014年9月17日6,369后缀自动机