题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4622
题意：给定一个长度不超过2000的字符串，之后有Q次区间查询（Q <= 10000），问区间中不同的子串数为多少？
学习资料： 知乎
SAM解析：
看了clj的PPT，对于最后为什么这样子插入节点还是有些不懂... 下面先讲讲一些理解
1.找出母串A中的所有子串可以看做是先找出A串的所有后缀，再在后缀中找出前缀（后缀中找前缀）；其中的init（初始状态）是指可以匹配所有后缀的原始状态，即可以对每个后缀进行trans(init,suf)到end状态，不要想着从A串开头进行匹配；
2.一个状态s由所有Right集合是Right(s)的字符串组成
Right集合相同只能说明串之间构成包含关系，如a,b子串的Right集合相同，并且max(a) < min(b)只能说明a是b串的后缀。
注：其中的max、min表示的是在母串中出现的结束位置所构成的集合为Right时的字符串（不止一个）的长度的最大/小值；
3.在构造后缀自动机时，step表示该字符所在的后缀的下标，即每次在前一个字符的基础之上+1.并且由于前一字符的Right集合中包含L+1，但是要使得状态能够通过字符为ch的边转移还需要g[][v]不等于0，这时就需要回溯到某一个g[][v] ！= 0的祖先节点。
注：祖先节点的Right包含后代节点，因为祖先节点表示的路径是后代节点路径的后缀，出现的位置更多；
4.step表示的含义？以及为何插入查找的原理？
令当前还未插入的状态为trans(init,T),其中T表示A[1...L-1]，当前待插入的字符x为A[L]，其中step[x] = L+1,（step表示字符x是当前要建的后缀自动机字符串的第几个）之后在Right集合含有L的状态中查找第一个可通过边x转移的状态p，
如果不考虑子串是否相同，则Tx的后缀数量为step[x]，由于是按照pre向上查找的，所以当找到p时，我们需要知道以p为后缀的子串有多少也是以x为后缀的？
这时候就用到了“压缩”，因为p的父节点们都符合条件（父节点的Right[L] = x,都是Tx的后缀），只需要压缩q和q的父节点p的空隙（step之间的差值为1），即可知道在状态为Tx时，有多少Tx的后缀已经存在~~,这时相减即可知道新添加的子串数量；
代码参考：JeraKrs
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; #define maxn 2007
#define SIGMA_SIZE 26 struct SAM{
int sz,tot,last;
int g[maxn<<][SIGMA_SIZE],pre[maxn<<],step[maxn<<]; void newNode(int s){
step[++sz] = s;
pre[sz] = ;
memset(g[sz],,sizeof(g[sz]));
} void init(){
tot = ;
sz = ; last = ;
newNode();
} int idx(char ch){return ch - 'a';} int Insert(char ch){
newNode(step[last]+);
int v = idx(ch), p = last, np = sz; while(p && !g[p][v])
g[p][v] = np,p = pre[p]; //知道找到Right集合中包含x的边的祖宗节点 if(p){
int q = g[p][v];
if(step[q] == step[p] + )
pre[np] = q;
else{
newNode(step[p]+);
int nq = sz; //nq替换掉q节点
for(int i = ;i < SIGMA_SIZE;i++)
g[nq][i] = g[q][i]; pre[nq] = pre[q];
pre[np] = pre[q] = nq; while(p && g[p][v] == q)
g[p][v] = nq,p = pre[p];
}
}
else pre[np] = ; tot += step[np] - step[pre[np]];
last = np;
return tot;
}
}SA;
char str[maxn];
int ans[maxn][maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%s",str);
int len = strlen(str);
for(int i = ;i < len;i++){
SA.init();
for(int j = i;j < len;j++){
ans[i][j] = SA.Insert(str[j]);
}
}
int Q, l, r;
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&l,&r);
printf("%d\n",ans[--l][--r]);
}
}
}