题意： 给定一个循环字符串，问字典序最小的串的开始位置。 思路： 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。 参照张天扬的论文： 把原串复制一遍到后面，然后构建后缀自动机。 从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。 如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。 /* *********************************************** Author :111qqz Created Time …

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意： 给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。 思路： 观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。 我们先考虑如何处理整个区间中，本质不同的子串数量。 考虑SAM，由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串，同时后缀自动机是最简的，所以问题也就变成了从初始状态开始不同路径的数量。 每个节点 u 表示的子串长度在 [min[u],max[u]]范围内. 又由于max(u.fail) = min(u)-1 因此u表示的子串的长度就是变成 …

题意： 给出2个字符串(2.5E5)，问最长公共子串的长度。 思路： 拿一个串建SAM 由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了 20171110UPdate:我好像说得太简略了。。 参考clj的冬令营讲稿： * 给两个长度小于100000的字符串A和B，求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM * 对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代表的是结束位置在r的，长度在[Min(s),Max(s)]之间的所有子串。 * 我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹配的最大长度L，那么min(L,Max(s))就可以更 …