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

题意：

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

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

思路：

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

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

题意：

有n个任务，第i个任务需要时间xi来完成，并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。

给你任务信息，问你最短需要多少时间来完成任务。

https://vjudge.net/problem/47450/origin

题意：

有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？

思路：

想到了预处理每个数最左最右的，最远的互质的数的范围。。

之后对于询问区间[l,r]，我们要知道 对于 i>=L && i <= R 并且 a[i].l<=L，a[i].r>=R的i的个数...

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

题意：

给一个DAG,现要从一条入度为0的点到一个出度为0的点，问最大点权和。

思路：

其实比较容易想到搜...不过复杂度会炸？

由于到一个点的最大点权和，需要更新完所有到达它的路线之后才能确定。

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

题意：

有 n * m - 1 个数，每次选择第 1,p + 1,p * 2 + 1….. 的顺序选择数，先按左到右，再按从上到下的顺序填入n * m 的格子，空格子可以和相邻的数字交换位置，问最后能否在格子中形成 1~ n * m - 1的数按从左到右，从上到下的顺序。

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

题意：

将格式混乱的html代码输出成标准格式。

思路：

模拟。

说下细节：

  * 遇到open tag,先打印，后dep++
  * 遇到close tag,先dep--,再打印
  * 遇到空标签，直接在当前深度打印
  * 遇到空白字符时，只有当前面出现了text以及后面也出现了text的时候才打印。**也就是说第一个string和最后一个string都是紧邻标签的。**

最坑的一点是...虽然题目给了数据组数，但是在所在行的同一行，可能出现下一组的开始

***在学习后缀自动机之前需要熟练掌握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上面跑就行了