AC. 梦想

字符串目录下的文章

[ZJOI 2013] 丽洁体

题意简述 给定一个串s。 现在你需要删去尽量少的字符,让其可以和模板串a*b*c匹配。 其中a,b,c是三个串,*可以匹配0个或多个字符。 1 \le |s|, |a|, |b|, |c| \le 50000,保证每个字符出现不超过500次。 算法讨论 难得的清真题。 考虑一个暴力。设f(i,j)为考虑到s的第i个字符,……
17/03/01 | 暂无评论 | 396阅读 阅读详情

[NOI 2016] 优秀的拆分

题目描述 如果一个字符串可以被拆分为AABB的形式,其中A和B是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串aabaabaa,如果令A=aab,B=a,我们就找到了这个字符串拆分成AABB的一种方式。 一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分……
16/08/06 | 暂无评论 | 873阅读 阅读详情

[NOI 2015] 品酒大会

题目描述 一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节,分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项,吸引了众多品酒师参加。 在大会的晚餐上,调酒师 Rainbow 调制了n杯鸡尾酒。这n杯鸡尾酒排成一行,其中第i杯酒1 \le i \le n被贴上了……
16/05/12 | 暂无评论 | 852阅读 阅读详情

[SDOI 2016] 生成魔咒

题目描述 魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符1,2拼接起来形成一个魔咒串[1,2]。 一个魔咒串S的非空子串被称为魔咒串S的生成魔咒。 例如S=[1,2,1]时,它的生成魔咒有[1],[2],[1,2],[2,1],[1,2,1]五种。S=[1,1,1]时,它的生成魔咒有[1],[1,1],[1,……
16/04/23 | 暂无评论 | 860阅读 阅读详情

[ZJOI 2015] 诸神眷顾的幻想乡

题目描述 幽香是全幻想乡里最受人欢迎的萌妹子,这天,是幽香的2600岁生日,无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 粉丝们非常热情,自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 这时幽香发现了一件非常有趣的事情,太阳花田有n块空地。在……
16/02/10 | 1 条评论 | 2,231阅读 阅读详情

[BZOJ 2754] 喵星球的点名

题目描述 a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。 假设课堂上有N个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必……
16/02/09 | 暂无评论 | 1,801阅读 阅读详情

[BZOJ 2780] Sevenk Love Oimaster

题意简述 给定n(n<=10000)个模板串和q(q<=60000)个询问串,求每个询问串是多少个模板串的子串。 模板串总长不超过100000,询问串总长不超过360000。 题目解析 初学后缀自动机,第一题~~ 然而看了题解才明白。 首先对n个串构造广义后缀自动机。所谓广义后缀自动机,就是内……
16/02/09 | 1 条评论 | 581阅读 阅读详情

[NOI 2014] 动物园

题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。 某天,园长给动物们讲解KMP算法。 园长:“对于一个字符串S,它的长度为……
16/01/10 | 暂无评论 | 1,885阅读 阅读详情

[BZOJ 3172] 单词

题目描述 某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。 输入格式 第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N
15/11/22 | 暂无评论 | 985阅读 阅读详情

AC自动机和Fail树

一直对AC自动机有种执念,觉得有它就能自动AC,是种特别神奇的算法,今天终于见识了。实际上,学习了AC自动机以后,才发现并没有那么玄乎。   一、Trie(字典树/前缀树) 学习AC自动机前,需要学会字典树。字典树,顾名思义当然是一棵树。特殊地,这棵树上的边是字符。那么……
15/11/22 | 暂无评论 | 5,244阅读 阅读详情