后缀自动机（其二）

今天刷了几个SAM的题，主要是关于SAM的tire树遍历和如何使用map实现tire树的。

由难到简单的来吧。

首先
P4070 [SDOI2016]生成魔咒

这个题和昨天做的题基本一模一样，只需要统计在插入过程中产生多少个不同的字符串，多少个字符串显然就是目前节点的最小长度和最大长度做差加一。
但是不一样的是这个题的单位元素是数组，并且可以到1e9。所以朴素的二维数组tire树肯定不行，考虑一手map映射。

主要增加知识点：map构建tire树，map的复杂度

注意必须用unorderedmap，否则会出现很多问题

算是变型模板吧

#include
using namespace std;
#define int long long
const int N=1e5+100;
char s[N];
int n,m,ans=0;
unordered_map<int,int>tire[N<<1];

struct SuffixAutoMaton
{
    //vectorright[N<<1];
   // int tire[N<<1][26]/*如果确定了只有小写字母再用26吧,这tire树*/;
    int fail[N<<1],len[N<<1]/*fail数组，len和上方说的一样*/;
    int size[N<<1];/*在build函数的第五个for循环执行完之后得到的size[i]代表了节点i所代表的的right集合大小，也就可以说是节点i代表了几个子串*/
    int last,tot,k[N<<1],c[N<<1];/*用于在构建树的时候使用*/
    void init()
    {
        last=tot=1;//初始化没什么好说的吧，注意last和tot从1开始
        tire[1].clear();
       // memset(tire[1],0,sizeof tire[1]);
    }
    void ins(int c)//传入当前插入的第i个字符，和i
    {
        int p=last;//上一个构建的节点是last，现在让p暂存last
        int np=++tot;//现在要构建的节点
        last=np;//更新last，你也可以把这一步放在后面
        len[np]=len[p]+1;//自然现在新构建的节点的最长长度是上一个节点的最长长度+1
        //tire[tot].clear();
        //memset(tire[tot],0,sizeof tire[tot]);//初始化这一层的tire数
        for(;p&&!tire[p][c];p=fail[p])//构建tire树
            tire[p][c]=np;
        if(!p)//构建fail树的第一种情况，
            fail[np]=1;
        else//第二种
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else//第三种
            {
                int nq=++tot;//nq，我们在第三种情况下和第二种情况发生了本质的变化，我们再也不能通过现存节点来找到符合约定的fail节点，只能自己生成一个。第三种情况内部显然可以对nq的信息加以统计
                len[nq]=len[p]+1;
                tire[nq]=tire[q];
               // memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        ans+=len[np]-len[fail[np]];
        size[np]=1;
       // right[np].push_back(pos);//把right集求出
    }
    void build(int n)
    {
        init();
        for(int i=1,temp;i<=n;i++)
        {
            cin>>temp;
            ins(temp);//插入节点
            cout<<ans<<endl;
        }
        return ;
        for(int i=1;i<=tot;i++) c[len[i]]++;//下面三个是排序，不动
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;

        for(int i=tot;i;i--)//这一步获取right集合right集大小，
        {
            int now=k[i];
            size[fail[now]]+=size[now];//求出了节点i的right集合大小
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
   // n=strlen(s+1);
    sam.build(n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

SUBLEX - Lexicographical Substring Search

SPOJ的一个题，可以在vjudge上交。
题意：我们有一个字符串，现在做k次询问，每次问字典序第k小的子串是谁。

这题就有意思了。要做好这个题你必须知道tire树的构建 ，整个节点排序的过程，怎样跑tire树。
也就是说这回要涉及原理的理解了。

首先，我们先看看对节点桶排序结束之后节点是什么样子。老样子我们还是拿出aababa的例子。

桶排序结束后节点的顺序为：1 2 7 9 3 4 5 6 8（主要是个拓扑序，别太在意程序实际跑的顺序）
而后size统计的结果对应是： 6 4 2 2 1 1 1 1 1 //这里统计的结果是相同子串在不同位置算作不同情况的
我们设一个sum数组，sum[i]表示i节点和之前统计过的节点代表有多少个字符串。
现在假设我们要求第kth个,我们就从第一个开始（注意1号节点的size和sum都给0）
之后按照先跑小字典序节点后的原则从第一个节点跑到最后，如果kth大于目前跑的节点指向节点的sum值，那么就输出这个字母并且让kth减去这个sum值。

#include
using namespace std;
#define int long long
const int N=5e5+100;
char s[N];
int n,m,t,kth;

struct SuffixAutoMaton
{
    vector<int>right[N<<1];
    int tire[N<<1][26]/*如果确定了只有小写字母再用26吧,这tire树*/;
    int fail[N<<1],len[N<<1]/*fail数组，len和上方说的一样*/;
    int size[N<<1];/*在build函数的第五个for循环执行完之后得到的size[i]代表了节点i所代表的的right集合大小，也就可以说是节点i代表了几个子串*/
    int last,tot,k[N<<1],c[N<<1];/*用于在构建树的时候使用*/
    int sum[N<<1];
    void init()
    {
        last=tot=1;memset(tire[1],0,sizeof tire[1]);//初始化没什么好说的吧，注意last和tot从1开始
    }
    void ins(int c,int pos)//传入当前插入的第i个字符，和i
    {
        int p=last;//上一个构建的节点是last，现在让p暂存last
        int np=++tot;//现在要构建的节点
        last=np;//更新last，你也可以把这一步放在后面
        len[np]=len[p]+1;//自然现在新构建的节点的最长长度是上一个节点的最长长度+1
        memset(tire[tot],0,sizeof tire[tot]);//初始化这一层的tire数
        for(;p&&!tire[p][c];p=fail[p])//构建tire树
            tire[p][c]=np;
        if(!p)//构建fail树的第一种情况，
            fail[np]=1;
        else//第二种
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else//第三种
            {
                int nq=++tot;//nq，我们在第三种情况下和第二种情况发生了本质的变化，我们再也不能通过现存节点来找到符合约定的fail节点，只能自己生成一个。第三种情况内部显然可以对nq的信息加以统计
                len[nq]=len[p]+1;
                memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        size[np]=1;
        right[np].push_back(pos);//把right集求出
    }
    void build(int n)
    {
        init();
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);//插入节点
        for(int i=1;i<=tot;i++) c[len[i]]++;//下面三个是排序，不动
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;//此时k数组记录的是拓扑序的节点
        for(int i=tot;i;i--)//这一步获取right集合right集大小，模范
        {
            int now=k[i];
           // if(t)
           // size[fail[now]]+=size[now];//求出了节点i的right集合大小，也就是不同位置的子串算作多个子串
           //else
            size[now]=1;
        }

        size[1]=0;
        for(int i=tot;i;i--)
        {
            sum[k[i]]=size[k[i]];
            for(int j=0;j<26;j++)
            {
                if(tire[k[i]][j])
                {
                    sum[k[i]]+=sum[tire[k[i]][j]];
                } 
            }
        }
        for(cin>>t;t;t--)
        {
             cin>>kth;
             int temp=1;
             while(kth-size[temp]>0)
             {
                kth-=size[temp]
                int p=0;
                while(kth>sum[tire[temp][p]])
                kth-=sum[tire[temp][p++]];
                temp=tire[temp][p];
                cout<<(char)('a'+p);
            }
            cout<<endl;
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    sam.build(n);
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

P3975 [TJOI2015]弦论

这个题和上面那个题唯一的区别就是：不同位置的同样子串是否算作多种情况。
显然至少对right集的操作。如果right集有东西那么无论有多少个都视为一个就可以了。

#include
using namespace std;
#define int long long
const int N=5e5+100;
char s[N];
int n,m,t,kth;

struct SuffixAutoMaton
{
    vector<int>right[N<<1];
    int tire[N<<1][26]/*如果确定了只有小写字母再用26吧,这tire树*/;
    int fail[N<<1],len[N<<1]/*fail数组，len和上方说的一样*/;
    int size[N<<1];/*在build函数的第五个for循环执行完之后得到的size[i]代表了节点i所代表的的right集合大小，也就可以说是节点i代表了几个子串*/
    int last,tot,k[N<<1],c[N<<1];/*用于在构建树的时候使用*/
    int sum[N<<1];
    void init()
    {
        last=tot=1;memset(tire[1],0,sizeof tire[1]);//初始化没什么好说的吧，注意last和tot从1开始
    }
    void ins(int c,int pos)//传入当前插入的第i个字符，和i
    {
        int p=last;//上一个构建的节点是last，现在让p暂存last
        int np=++tot;//现在要构建的节点
        last=np;//更新last，你也可以把这一步放在后面
        len[np]=len[p]+1;//自然现在新构建的节点的最长长度是上一个节点的最长长度+1
        memset(tire[tot],0,sizeof tire[tot]);//初始化这一层的tire数
        for(;p&&!tire[p][c];p=fail[p])//构建tire树
            tire[p][c]=np;
        if(!p)//构建fail树的第一种情况，
            fail[np]=1;
        else//第二种
        {
            int q=tire[p][c];
            if(len[p]+1==len[q])
                fail[np]=q;
            else//第三种
            {
                int nq=++tot;//nq，我们在第三种情况下和第二种情况发生了本质的变化，我们再也不能通过现存节点来找到符合约定的fail节点，只能自己生成一个。第三种情况内部显然可以对nq的信息加以统计
                len[nq]=len[p]+1;
                memcpy(tire[nq],tire[q],sizeof(tire[q]));
                fail[nq]=fail[q];
                fail[q]=fail[np]=nq;
                for(;tire[p][c]==q;p=fail[p])
                tire[p][c]=nq;
            }
        }
        size[np]=1;
        right[np].push_back(pos);//把right集求出
    }
    void build(int n)
    {
        init();
        for(int i=1;i<=n;i++) ins(s[i]-'a',i);//插入节点
        for(int i=1;i<=tot;i++) c[len[i]]++;//下面三个是排序，不动
        for(int i=1;i<=tot;i++) c[i]+=c[i-1];
        for(int i=1;i<=tot;i++) k[c[len[i]]--]=i;

        for(int i=tot;i;i--)//这一步获取right集合right集大小，
        {
            int now=k[i];
            if(t)
            size[fail[now]]+=size[now];//求出了节点i的right集合大小，也就是不同位置的子串算作多个子串
            else
                size[now]=1;
        }
        size[1]=0;
        for(int i=tot;i;i--)
        {
            sum[k[i]]=size[k[i]];
            for(int j=0;j<26;j++)
            {
                if(tire[k[i]][j])
                {
                    sum[k[i]]+=sum[tire[k[i]][j]];
                }
            }
        }
        if(kth>sum[1])
        {
            cout<<-1;
            return ;
        }
        int temp=1;
        while(kth-size[temp]>0)
        {
            kth-=size[temp];
            int p=0;
            while(kth>sum[tire[temp][p]])
                kth-=sum[tire[temp][p++]];
            temp=tire[temp][p];
            cout<<(char)('a'+p);
        }
    }
}sam;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    cin>>t>>kth;
    sam.build(n);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104