SPOJ – LCS Longest Common Substring 后缀自动机
Longest Common Substring 后缀自动机 Source SPOJ - LCS My Solution 题意：求两个字符串的最长公共子串。 后缀自动机 看了很久 WJMZBMR 讲后缀自动机的ppt才大致把后缀自动机搞懂^_^, 此外附上两个比较好的…
CSU – 1632 Repeated Substrings 后缀数组、distinct substring
Repeated Substrings 后缀数组、distinct substring Source CSU - 1632 My Solution 题意：给出一个字符串，找出出现2次及以上的子串的种数。 后缀数组 跑出sa数组和height数组，然后从i = 2 ~ n遍历，每次 ans +=…
POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表
Stammering Aliens 后缀数组、二分、二叉堆、ST表 Source POJ - 3882 2009 South Western European Regional Contest My Solution 题意：给出一个字符串，要求找出至少出现m次的最长子串长度。 后缀数组、二分、二…
HDU – 2457 DNA repair AC自动机+dp
D - DNA repair AC自动机+dp Source HDU 2457 My Solution 题意：给出n个模式串，给出一个主串，要求在主创上改动尽可能少的字符，使任一模式串不在主串中出现。 AC自动机+dp 按照一般的 AC自动机+dp转移 的模式(…
POJ – 3415 Common Substrings 后缀数组+单调栈+前缀和
Common Substrings 后缀数组+单调栈+前缀和 Source POJ - 3415 My Solution 题意：给出两个字符串，求出它们的相同的长度至少为k的子串的个数。 后缀数组+单调栈+前缀和 把a、b这两个字符串用'#'连起来，然后求出…
HDU – 4763 Theme Section KMP
C - Theme Section KMP Source HDU - 4763 My Solution 题意：给出一个字符串，找出一个尽可能长的子串，要求其在字符串的开头结尾中间都出现且不能有重叠。 KMP 先对主串跑出next数组，然后对于ptr = n，从nxt[n]…
HDU – 5384 Danganronpa AC自动机、简单题
Danganronpa AC自动机、简单题 Source HDU - 5384 My Solution 题意：给出n个主串、m个模式串，求每个主串Ai中这m个模式串出现的次数和。 AC自动机、简单题 把n个模版串丢到一个队列里，然后读取m个模式串建立AC自…
UVA – 11475 Extend to Palindrome manacher+贪心
E - Extend to Palindrome manacher+贪心 Source UVA - 11475 My Solution 题意：给出一个字符串，在末尾添加尽可能少的字符串，使这个新字符串为回文串，输出新字符串。 manacher+贪心 先用manacher O(n)的跑出…
UESTC 8 God Only Knows! AC自动机
God Only Knows! AC自动机 Source The 11th UESTC Programming Contest Final UESTC 8 God Only Knows! My Solution 题意：给一个字符串s，然后给出n个字符串stri，问s的不包…
UESTC 1384 卿大爷的多个女友 后缀数组、最长连续重复子串
卿大爷的多个女友 后缀数组、最长连续重复子串 Source 2016 UESTC Training for Search Algorithm & String UESTC 1384 卿大爷的多个女友 My Solution 题意：给一个字符串s，求最长连续重复子串的长度，…
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) D. Dense Subsequence ST表+贪心
D. Dense Subsequence ST表+贪心 My Solution ST表+贪心 ST表，用O(nlogn)的预处理，然后O(1)查询，找出ans中出现的最大的字母， 然后把比它小的字母都从小到大push到ans里， 然后贪心的去那个需要的最大字母的个…
2016 UESTC Training for Search Algorithm & String I – 谭爷剪花布条 KMP
I - 谭爷剪花布条 KMP Source 2016 UESTC Training for Search Algorithm & String My Solution KMP 套版题 与自己收藏的模版唯一不同的是这里是子串不能重叠的，恰好自己的模版是返回一个vector存…
2016 UESTC Training for Search Algorithm & String H – 中二少女与字符串 Trie 字典树
H - 中二少女与字符串 Trie 字典树 Source 2016 UESTC Training for Search Algorithm & String My Solution Trie 字典树 分别求以l为起始点的字符串有多少个前缀符合条件，答案即为和…
2016 UESTC Training for Search Algorithm & String K – 卿大爷的三个女友 KMP、跳转数组
K - 卿大爷的三个女友 KMP、跳转数组 Source 2016 UESTC Training for Search Algorithm & String My Solution KMP 的跳转数组的拓展使用 关键在于KMP思维的转化。思维很重要！先用文本串…
