标签 - AC自动机

? 解题记录 ? ? 洛谷 ? ? AC自动机 ? ? 矩阵快速幂 ? ? 最短路 ?    2018-06-27 22:01:21    559    0    0
题目描述  给出n个互不包含的字符串,要求你求出一个最短的字符串S,使得这n个字符串在S中总共至少出现m次,问S最短是多少   (, ), 总字符不超过  。  输入格式: 第一行两个整数n, m 接下来n行n个字符串 输出格式:  一行表示最短长度。   输入输出样例输入样例#1: 复制4 5 monika tomek szymon bernard 输出样例#1: 复制23​  ​  这题好想,就是处理每一个字符串AC自动机结尾到另一个结尾的最短路矩阵
? 解题记录 ? ? 洛谷 ? ? AC自动机 ?    2018-06-24 23:00:06    603    0    0
题目描述二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。 示例: 例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。 任务: 请写一个程序: 1.在文本文件WIR.IN中读入病毒代码; 2.判断是否存在一个无限长的安全代码; 3.将结果输出到文件WIR.OUT中。 输入输出格式输入格
? 解题记录 ? ? HDU ? ? AC自动机 ? ? 线段树 ?    2018-05-22 21:58:34    671    0    0
GRE WordsTime Limit: 30000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5466    Accepted Submission(s): 678 Problem Description Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviou
? 解题记录 ? ? AC自动机 ? ? 洛谷 ? ? 模板 ?    2018-04-04 17:05:09    528    0    0
题目背景这是一道简单的AC自动机模板题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意 题目描述给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。 输入输出格式输入格式:   第一行一个n,表示模式串个数; 下面n行每行一个模式串; 下面一行一个文本串。   输出格式:   一个数表示答案   输入输出样例输入样例#1: 复制2 a aa aa 输出样例#1: 复制2 说明subtask1[50pts
? 解题记录 ? ? AC自动机 ? ? HDU ?    2018-01-16 14:55:53    410    0    0
Problem Description > The Eternal Fleet was built many centuries ago before the time of Valkorion by an unknown race on the planet of Iokath. The fate of the Fleet's builders is unknown but their legacy would live on. Its first known action was in the annihilation of all life in Wild Space. It sp
? 集训题目 ? ? AC自动机 ? ? 动态规划 ? ? 解题记录 ?    2018-01-15 22:18:59    510    0    0
【题目描述】 给定正整数m以及n个01串s1~sn,你需要求出长度为2m的反对称的包含这n个01串作为子串的01串的个数。对998244353取模。 一个01串s是反对称的当且仅当它对于1<=i<=|s|都满足s[i]≠s[|s|-i+1]。 【输入数据】 第一行两个整数n,m。接下来n行每行一个字符串s1~sn。 【输出数据】 一行一个整数表示答案。 【样例输入】        2 3        011     &nb
? 解题记录 ? ? 洛谷 ? ? AC自动机 ?    2017-11-18 17:07:44    337    0    0
题目描述有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。 输入输出格式输入格式:  输入含多组数据。 每组数据的第一行为一个正整数NN,表示共有NN个模式串,1 \leq N \leq 1501≤N≤150。 接下去NN行,每行一个长度小于等于7070的模式串。下一行是一个长度小于等于10^6106的文本串TT。 输入结束标志为N=0N=0。   输出格式:  对于每组数据,第一行输出模式串最多出现的次数,接下去若干行每行输出一个出现次数最多的模式串,按输入顺序排列。 &nbs