分类 - 字符串算法

? 解题记录 ? ? 洛谷 ? ? 哈希 ? ? Manacher ?    2018-07-11 16:50:30    302    0    0
描述:给定一个多边形,求对称轴数量。n <= 1000000   输入输出样例输入样例#1: 复制2 12 1 -1 2 -1 2 1 1 1 1 2 -1 2 -1 1 -2 1 -2 -1 -1 -1 -1 -2 1 -2 6 -1 1 -2 0 -1 -1 1 -1 2 0 1 1 输出样例#1: 复制4 2​​       
? 解题记录 ? ? 洛谷 ? ? AC自动机 ? ? 矩阵快速幂 ? ? 最短路 ?    2018-06-27 22:01:21    570    0    0
题目描述  给出n个互不包含的字符串,要求你求出一个最短的字符串S,使得这n个字符串在S中总共至少出现m次,问S最短是多少   (, ), 总字符不超过  。  输入格式: 第一行两个整数n, m 接下来n行n个字符串 输出格式:  一行表示最短长度。   输入输出样例输入样例#1: 复制4 5 monika tomek szymon bernard 输出样例#1: 复制23​  ​  这题好想,就是处理每一个字符串AC自动机结尾到另一个结尾的最短路矩阵
? 解题记录 ? ? 洛谷 ? ? 线段树 ? ? 哈希 ?    2018-06-25 20:28:33    488    0    0
题目描述The Trains of Colour Parade begins tomorrow in Byteotia. Intense preparations are already in progress at the station's auxiliary tracks. There are nn parallel tracks at the station, numbered from 11 to nn . The train no. ii occupies the i^{th}ith 
? 解题记录 ? ? 洛谷 ? ? AC自动机 ?    2018-06-24 23:00:06    616    0    0
题目描述二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。 示例: 例如如果{011, 11, 00000}为病毒代码段,那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段,那么就不存在一个无限长的安全代码。 任务: 请写一个程序: 1.在文本文件WIR.IN中读入病毒代码; 2.判断是否存在一个无限长的安全代码; 3.将结果输出到文件WIR.OUT中。 输入输出格式输入格
? 解题记录 ? ? HDU ? ? AC自动机 ? ? 线段树 ?    2018-05-22 21:58:34    685    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
? 解题记录 ? ? 洛谷 ? ? 哈希 ?    2018-05-05 22:51:30    254    0    0
题目描述We consider strings consisting of lowercase letters of the English alphabet in this problem. An initial fragment of a given string is called its prefix. A final (terminal) fragment of a given string is called its suffix. In particular, the empty string is both a prefix and a suffix of any string
? 解题记录 ? ? AC自动机 ? ? 洛谷 ? ? 模板 ?    2018-04-04 17:05:09    540    0    0
题目背景这是一道简单的AC自动机模板题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意 题目描述给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。 输入输出格式输入格式:   第一行一个n,表示模式串个数; 下面n行每行一个模式串; 下面一行一个文本串。   输出格式:   一个数表示答案   输入输出样例输入样例#1: 复制2 a aa aa 输出样例#1: 复制2 说明subtask1[50pts
? 解题记录 ? ? 哈希 ?    2018-03-16 21:47:48    1189    0    0
【题目描述】给出一个 n × m 的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵 中出现了至少两次。输出最大正方形的边长。 【输入】第一行两个整数 n, m 代表矩阵的长和宽; 接下来 n 行,每行 m 个字符(小写字母) ,表示矩阵。 【输出】输出一个整数表示满足条件的最大正方形的边长。 【输入样例】5 10 ljkfghdfas isdfjksiye pgljkijlgp eyisdafdsi lnpglkfkjl 【输出样例】3 【提示】【数据规模】 对于 30%的数据,n,m≤100; 对于 100%的数据,n,m≤500。 对于本题,我们可以这样哈希:选择一个进制数
? 解题记录 ? ? BZOJ ? ? KMP ?    2018-03-13 07:41:00    416    0    0
Description一个串T是S的循环节,当且仅当存在正整数k,使得S是T^k(即T重复k次)的前缀,比如abcd是abcdabcdab的循环节 。给定一个长度为n的仅由小写字符构成的字符串S,请对于每个k(1<=k<=n),求出S长度为k的前缀的最短循环节的 长度per_i。字符串大师小Q觉得这个问题过于简单,于是花了一分钟将其AC了,他想检验你是否也是字符串大师。 小Q告诉你n以及per_1,per_2,...,per_n,请找到一个长度为n的小写字符串S,使得S能对应上per。 Input第一行包含一个正整数n(1<=n<=100000),表示字符串的长度。
? 解题记录 ? ? 字典树 ? ? Codeforces ?    2018-03-12 15:47:10    736    0    0
  Alice has a very important message M consisting of some non-negative integers that she wants to keep secret from Eve. Alice knows that the only theoretically secure cipher is one-time pad. Alice generates a random key K of the length equal to the message's length. Alice co