题目链接：http://codeforces.com/problemset/problem/123/D

题意：

如果字符串y在字符串x中出现n次，那么F(x,y)=n*(n+1)/2

http://poj.org/problem?id=3415

题意：

给出两个字符串，问公共长度大于等于k的子串个数（只要两个串的位置不同就认为是不同）

思路：

考虑SAM的性质。

SAM上的一个节点所能接受的本质不同的子串个数是**st[v].len - st[st[v].link].len**

http://acm.hdu.edu.cn/showproblem.php?pid=4416

题意：

给出一个字符串A和n个字符串B,问A的子串中，不在任何一个B中出现的本质不同的子串有多少。

思路：

还是根据len搞事情

我们知道，如果不加任何条件，SAM中一个节点所表示的本质不同的子串数量是st[i].len - st[st[i].link].len

http://acm.hdu.edu.cn/showproblem.php?pid=3518

题意：

给一个字符串，问字符串中，至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路：

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5558

题意：

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i - 1]开始的所有后缀中最大匹配的公共前缀长度

思路：

这个动态的过程很容易想到SAM啊。。

题意：

求n个串的最长公共子串，n<=10

思路：

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

首先参考下2个串的LCS的做法spoj-lcs

http://acm.hdu.edu.cn/showproblem.php?pid=4436

题意：

给出n个仅由数字组成的字符串，问n个字符串的所有不同子串的和。

思路：

SAM水题

从初始状态开始，走过所有路径，就是该SAM表示的所有的（不重复）子串。

http://www.spoj.com/problems/SUBLEX/en/

题意：

给一个字符串，每次询问字典序第k大的不重复子串。

思路：

先做个拓扑dp，求出SAM上，一个状态到种态的路径数。

拓扑dp其实就是按照拓扑序的dp啦…

http://www.spoj.com/problems/NSUBSTR/en/

题意：

f[i]指长度为i的串出现次数的最大值。这里的不同出现指，可以有重复串，只要起始位置不同就视为不同的出现。

求f[1]..f[lenth]。

思路：

我们知道，SAM上的节点是right集合的等价类。

***在学习后缀自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机***

怕是老年人的最后一篇算法学习笔记了

心情不好，此文无限期tj

概述

主要讲解在我学习的过程中比较难理解的地方..并不保证全面

题意：

给定一个循环字符串，问字典序最小的串的开始位置。

思路：

之前用poj 1509 解题报告-字符串的最小表示法   A过

字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。

http://acm.hdu.edu.cn/showproblem.php?pid=4622

题意：

给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。

思路：

观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。

题意：

给出2个字符串(2.5E5)，问最长公共子串的长度。

思路：

拿一个串建SAM

由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了