111qqz的小窝

老年咸鱼冲锋!

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D 题意: 如果字符串y在字符串x中出现n次

poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415 题意: 给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同) 思路: 考虑SAM的性质。 SAM上的一个节点所能接受

hdu 4416 Good Article Good sentence (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4416 题意: 给出一个字符串A和n个字符串B,问A的子串中,不在任何一个B中出现的本质不同的子串有多少。 思路: 还是根据len搞事情 我们知道,如果不

hdu 3518 Boring counting (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=3518 题意: 给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。 思路: 考虑SAM

hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice's Classified Message (后缀自动机)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5558 题意: 说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i - 1]开始的所有后缀中最大匹配的公共前缀长度 思路:

SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意: 求n个串的最长公共子串,n<=10 思路: 不会啊orz 先放一波参考资料&题解好了。 codeforces_Understanding Suffix Automaton in depth code风景区_spoj_lc

hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机,多串建立)

http://acm.hdu.edu.cn/showproblem.php?pid=4436 题意: 给出n个仅由数字组成的字符串,问n个字符串的所有不同子串的和。 思路: SAM水题 从初始状态开始,走过所有路径,就是该SAM表示的所有的

SPOJ SUBLEX Lexicographical Substring Search ( 后缀自动机)

http://www.spoj.com/problems/SUBLEX/en/ 题意: 给一个字符串,每次询问字典序第k大的不重复子串。 思路: 先做个拓扑dp,求出SAM上,一个状态到种态的路径数。 拓扑dp其实就是按照拓扑

spoj nsubstr Substrings (后缀自动机 模板题)

http://www.spoj.com/problems/NSUBSTR/en/ 题意: f[i]指长度为i的串出现次数的最大值。这里的不同出现指,可以有重复串,只要起始位置不同就视为不同的出现。 求f[1]..f[lent

【施工中】SAM学习笔记

怕是老年人的最后一篇算法学习笔记了心情不好,此文无限期tj概述 主要讲解在我学习的过程中比较难理解的地方..并不保证全面 首先,后缀自动机是一个

poj 1509 Glass Beads (后缀自动机求最小循环表示)

题意: 给定一个循环字符串,问字典序最小的串的开始位置。 思路: 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n

hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意: 给一个字符串,给出若干询问,每组询问给一个区间[l,r],问区间中本质不同的字符串的个数。 思路: 观察发现,有10000组查询,字符串

SPOJ LCS Longest Common Substring (后缀自动机模板题)

题意: 给出2个字符串(2.5E5),问最长公共子串的长度。 思路: 拿一个串建SAM 由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿