hdu 4622 Reincarnation SAM模板题

题目链接：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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 #define maxn 2007
 7 #define SIGMA_SIZE 26
 8 
 9 struct SAM{
10     int sz,tot,last;
11     int g[maxn<<1][SIGMA_SIZE],pre[maxn<<1],step[maxn<<1];
12 
13     void newNode(int s){
14         step[++sz] = s;
15         pre[sz] = 0;
16         memset(g[sz],0,sizeof(g[sz]));
17     }
18 
19     void init(){
20         tot = 0;
21         sz = 0; last = 1;
22         newNode(0);
23     }
24 
25     int idx(char ch){return ch - 'a';}
26 
27     int Insert(char ch){
28         newNode(step[last]+1);
29         int v = idx(ch), p = last, np = sz;
30 
31         while(p && !g[p][v])
32             g[p][v] = np,p = pre[p];    //知道找到Right集合中包含x的边的祖宗节点
33 
34         if(p){
35             int q = g[p][v];
36             if(step[q] == step[p] + 1)
37                 pre[np] = q;
38             else{
39                 newNode(step[p]+1);
40                 int nq = sz;             //nq替换掉q节点
41                 for(int i = 0;i < SIGMA_SIZE;i++)
42                     g[nq][i] = g[q][i];
43 
44                 pre[nq] = pre[q];
45                 pre[np] = pre[q] = nq;
46 
47                 while(p && g[p][v] == q)
48                     g[p][v] = nq,p = pre[p];
49             }
50         }
51         else pre[np] = 1;
52 
53         tot += step[np] - step[pre[np]];
54         last = np;
55         return tot;
56     }
57 }SA;
58 char str[maxn];
59 int ans[maxn][maxn];
60 int main()
61 {
62     int T;
63     scanf("%d",&T);
64     while(T--){
65         scanf("%s",str);
66         int len = strlen(str);
67         for(int i = 0;i < len;i++){
68             SA.init();
69             for(int j = i;j < len;j++){
70                 ans[i][j] = SA.Insert(str[j]);
71             }
72         }
73         int Q, l, r;
74         scanf("%d",&Q);
75         while(Q--){
76             scanf("%d%d",&l,&r);
77             printf("%d
",ans[--l][--r]);
78         }
79     }
80 }