字符串 - Page 5

「JoyOI1860」后缀数组
描述Description我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度，其中height[1]=0你的任务就是求出SA和height这两个数组。字符串长度<=200000输入格式InputFormat一行，为描述中的字符串（仅会出现小写字母）...
62014年9月4日4,488后缀数组

「BZOJ1692」[Usaco2007 Dec] 队列变换
DescriptionFJ打算带他的N(1<=N<=30,000)头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果FJ带去的奶牛依次为Bessie、Sylvia、Dora，登记人员就把这支队伍登记为BSD）。...
02014年7月7日6,010后缀数组
「BZOJ1717」[Usaco2006 Dec] Milk Patterns 产奶的模式
Description农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如12323231中2323出现了两次。当K=2时，这个长度为4。Input*Line1:两个整...
52014年5月20日6,049二分法,后缀数组
「JoyOI1519」博彩游戏
背景BackgroundBob最近迷上了一个博彩游戏……描述Description这个游戏的规则是这样的：每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。请你告诉Bob中奖的概率有多少？输入格式InputFormat第一行三个用空格隔开的数N、M和R的范围R。其中1<=R<=9...
02014年5月11日3,687递推与动规,AC自动机
「BZOJ1009」[HNOI2008] GT考试
Description阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.A1和X1可以为0Input第一行输入N,M,K.接下来一行输入M位的数。100%数据N<=10^9,M<=20,K<=100040%数据N<=100010%数据N<=6Output阿申想知道不出现不吉利数字的号...
62014年5月9日15,392递推与动规,KMP,矩阵乘法
「BZOJ1031」[JSOI2007] 字符加密Cipher
Description喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作： JSOI07SOI07JOI07JSI07JSO07JSOI7JSOI0把它们按照字符串的大小排序：07JSOI7JSOI0I07JSOJSOI07OI07JSSOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加...
42014年5月5日6,018后缀数组
「BZOJ1174」[Balkan2007] Toponyms
Description给你一个字符集合,你从其中找出一些字符串出来.希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.Input第一行给出数字N.N在[2,1000000]下面N行描述这些字符串,长度不超过20000总输入不超过20000字符Output asinglelinewithanintegerrepresentingthemaximallevelofcomplexity Lc(T).SampleInput7JoradeSusOrheiJoradeMijlocJoreniJoradeJosJapcaOrheiulVechiSampleOutput24题解首...
42014年4月2日4,627字典树
「hdu2222」Keywords Search
ProblemDescriptionInthemoderntime,SearchenginecameintothelifeofeverybodylikeGoogle,Baidu,etc.Wiskeyalsowantstobringthisfeaturetohisimageretrievalsystem.Everyimagehavealongdescription,whenuserstypesomekeywordstofindtheimage,thesystemwillmatchthekeywordswithdescriptionofimageandshowtheimagewhichthemostkeywordsbematched.Tosimplifytheproblem,givingyouadescriptionofimage,andsomekeywords,yousho...
42014年3月24日7,826AC自动机
「BZOJ1030」[JSOI2007] 文本生成器
DescriptionJSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章——也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，...
42014年3月24日8,721AC自动机
「POJ2001」Shortest Prefixes
DescriptionAprefixofastringisasubstringstartingatthebeginningofthegivenstring.Theprefixesof"carbon"are:"c","ca","car","carb","carbo",and"carbon".Notethattheemptystringisnotconsideredaprefixinthisproblem,buteverynon-emptystringisconsideredtobeaprefixofitself.Ineverydaylanguage,wetendtoabbreviatewordsbyprefixes.Forexample,"carbohydrate"iscommonlyabbreviatedby"carb".Inthisproblem,givenasetofwo...
02014年3月19日5,903字典树
「CODEVS1204」寻找子串位置(KMP)
题目描述 Description给出字符串a和字符串b，保证b是a的一个子串，请你输出b在a中第一次出现的位置。输入描述 InputDescription仅一行包含两个字符串a和b输出描述 OutputDescription仅一行一个整数样例输入 SampleInputabcdbc样例输出 SampleOutput2数据范围及提示 DataSize&Hint字符串的长度均不超过100Pascal用户请注意：两个字符串之间可能包含多个空格代码暴力不好玩，我们写个KMP吧KMP参看KMP...
32014年1月1日5,603KMP