111qqz的小窝

老年咸鱼冲锋!

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

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

Posted by 111qqz Monday, November 13, 2017

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

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

Posted by 111qqz Sunday, November 12, 2017

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

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

Posted by 111qqz Saturday, November 11, 2017

hdu 3518 Boring counting (后缀自动机)

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

Posted by 111qqz Saturday, November 11, 2017

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

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

Posted by 111qqz Saturday, November 11, 2017

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

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

Posted by 111qqz Saturday, November 11, 2017

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

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

Posted by 111qqz Thursday, November 9, 2017

SPOJ SUBLEX Lexicographical Substring Search （ 后缀自动机）

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

Posted by 111qqz Wednesday, November 8, 2017

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

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

Posted by 111qqz Wednesday, November 8, 2017

【施工中】SAM学习笔记

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

Posted by 111qqz Saturday, November 4, 2017

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

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

Posted by 111qqz Saturday, November 4, 2017

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

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

Posted by 111qqz Saturday, November 4, 2017

SPOJ LCS Longest Common Substring （后缀自动机模板题）

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

Posted by 111qqz Friday, November 3, 2017

FEATURED TAGS
bfs binary-search brute-force c++ dfs dp greedy hash km kmp leetcode math number-theory rmq sg函数 stl tensorflow 二分图最佳匹配 分块 前缀和 匈牙利算法 区间dp 博弈论 后缀自动机 图论 字符串 快速幂 数位dp 构造 树状数组 概率 模拟 母函数 矩阵 离散化 线段树 计算几何
ABOUT ME
avatar

ex-ACMer@HUST, researcher@SenseTime

FRIENDS