XIII Open Championship Problem E. Enter the Word Problem 后缀自动机+贪心
Problem E. Enter the Word 后缀自动机+贪心 Source XIII Open Championship of Y.Kupala Grodno SU Grodno, Saturday, April 29, 2017 My Solution 题意：这里对于生成一个字符串有2种操作，1、在末…
HDU 6208 The Dominator of Strings 后缀自动机
The Dominator of Strings 后缀自动机 Source 2017 ACM/ICPC Asia Regional Qingdao Online HDU 6208 The Dominator of Strings My Solution 题意：每组数据给出n个字符串，每组总共最多1e5个字符，然后要…
HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树
Fleet of the Eternal Throne 后缀数组+字典树 Source 2017 Multi-University Training Contest - Team 8 HDU 6138 My Solution 题意：给出n(n<=1e5)个字符串，且字符串的字符总和<=1e5，给出m个询问…
Petrozavodsk Winter-2013. Ural FU Contest Problem D. Five Palindromes manacher、一个串切割成5个回文子串、优化
Problem D. Five Palindromes manacher、一个串切割成5个回文子串、优化 Source Petrozavodsk Winter-2013. Ural FU Contest My Solution manacher、一个串切割成5个回文子串、优化 第一次使用manacher 嘿嘿☺☺ 为了…
Gym – 101164C Castle KMP的拓展、next数组+dp、好题
Problem C Castle KMP的拓展、next数组+dp、好题 Source ACM-ICPC Southeastern European Regional Programming Contest Bucharest, Romania – Vinnytsya, Ukraine Gym - 101164C My Solution 题意：给出原…
Gym – 101174E Passwords AC自动机+额外的限制条件+状态压缩dp
Problem E Passwords AC自动机+额外的限制条件+状态压缩dp Source SWERC'2016 Universidade do Porto Gym - 101174E My Solution 题意：给出n个由小写字母模式串，用大写字母、小写字母、十进制数字构造的…
HDU – 2222 Keywords Search AC自动机
Keywords Search AC自动机 Source HDU - 2222 My Solution 题意：给出n个字符串为这些字符串在主串s中出现的个数。 AC自动机 裸的AC自动机，注意下给定模式串可能有一些相同的串，然后按照主串在自动机上遍历即可…
UESTC 1066 Palindromic String manacher
Palindromic String manacher Source 2015 UESTC Training for Search Algorithm and String UESTC 1066 Palindromic String My Solution 题意：求出前缀的回文重数的和，（回文重数是递归定义的，详见题面）。 ma…
UESTC 1696 一道简单的字符串题 KMP+dp
一道简单的字符串题 KMP+dp Source 2017 UESTC Training for Search Algorithm & String UESTC 1696 一道简单的字符串题 My Solution 题意：求出所有前缀在字符串中出现次数的和 KMP+dp dpi表示前缀s[0,…
UESTC 1709 DNA序列 AC自动机+dp+矩阵快速幂优化
DNA序列 AC自动机+dp+矩阵快速幂优化 Source 2017 UESTC Training for Search Algorithm & String UESTC 1709 DNA序列 My Solution 题意：给出m(0<=m<=10)个模式串(0<len<=10)，用AGTC构造…
HDU – 2825 Wireless Password AC自动机+状压dp
Wireless Password AC自动机+状压dp Source HDU - 2825 My Solution 题意：给出一个字符串集合，集合里包含m(m <= 10)个长度不大于10的字符串，要求构造长度为n(1<=n<=25)的字符串且子串中至少出现k个集合…
UESTC 1582 奇迹的魔法啊，再度出现！ 二进制树(字典树的一种特殊情况)
奇迹的魔法啊，再度出现！二进制树 Source 17暑假前集训-数据结构专题 By AutSky_JadeK，思路非原创 2017 UESTC Training for Data Structures UESTC 1582 奇迹的魔法啊，再度出现！ My Solution 题意：给…
HihoCoder – 1449 后缀自动机三·重复旋律6 后缀自动机、递推、DFS
后缀自动机三·重复旋律6 后缀自动机、递推、DFS Source HihoCoder - 1449 My Solution 题意：求一个字符串中，所有长度为K的子串出现次数最多的子串的出现次数，但是K不是固定的，求所有的K的答案。 …
HihoCoder – 1445 后缀自动机二·重复旋律5 后缀自动机
后缀自动机二·重复旋律5 Source HihoCoder - 1445 My Solution 题意：统计字符串中不同子串的个数。 后缀自动机 这题是后缀自动机基础题，直接使用SAM上的pre树， sigma{val[np] - val[pre[np]]} 复…
URAL – 1158 Censored! AC自动机+dp
Censored! AC自动机+dp Source URAL - 1158 ACM ICPC 2001. Northeastern European Region, Northern Subregion My Solution 题意：给出n个不同的字符，用这n个字符构成长度为m的字符串，要求每个串的子串都不出现…
UVALive – 3703 Billing Tables Tire、字典树
Billing Tables Tire、字典树 Source UVALive - 3703, UVA - 1385, POJ - 3149 NEERC 2006 My Solution 题意：对于11位数字串(电话号码)，按优先级给定n个区间，每个区间有一个标记。若一个电话号码在某个区间内(…
HDU – 5769 Substring 后缀自动机+二分、新增distinct子串的个数和位置
Substring 后缀自动机+二分 Source HDU - 5769 My Solution 题意：每次给出一个字母ch和一个字符串s，求s中有多少个不同的子串含有字母ch。 后缀自动机+二分、新增distinct子串的个数和位置 首先这里要用到后缀自…
Codeforces 17E Palisection 回文自动机+邻接表
E. Palisection 回文自动机+邻接表 My Solution 题意：给出一个字符串要求找出多少对有相交部分的回文子串。 回文自动机+邻接表 首先，直接求这个问题比较麻烦，故可以转化为总的回文子串的对数减掉不相交…
URAL – 1960 Palindromes and Super Abilities 回文自动机
Palindromes and Super Abilities 回文自动机 Source URAL - 1960 My Solution 题意：逐个字符的添加一个字符串，问每添加一个字符显存的字符串的总不同的回文子串的个数。 回文树自动机 首先推荐篇比较好的讲回文…
HDU – 4622 Reincarnation 后缀自动机
Reincarnation 后缀自动机 Source HDU - 4622 My Solution 题意：给出一个长度<=2000的字符串，然后给出q<=10000个询问，为s[l,r]内有多少个不同的子串。 后缀自动机 首先n <= 2000，故可以用O(n^2)的算…
