# 史上全网最清晰后缀自动机学习（四）后缀自动机里的DAG结构

### 分析

```时间限制:15000ms

2
101
09

131```

endpos

sum

0

{0,1,2,3,4,5,6,7}

0

1

1

{1,2,5}

1

2

11

{2}

11

3

112

{3}

112

4

1122,122,22

{4}

1266

5

2

{3,4,6}

2

6

11221,1221,221,21

{5}

12684

7

112212,12212,2212,212

{6}

126848

8

12

{3,6}

12

9

1122124,122124,22124,2124,124,24,4

{7}

1248648

```状态6的sum其实=(状态5的sum*10+读入的1*状态6中包含的子串个数)+(状态4的sum*10+读入的1*状态4中包含的子串个数) =
(2*10+3)+(1266*10+1) = 12661+23=12684```

endpos

|validnum|

sum

S

{0,1,2,3,4,5,6}

1

0

1

1

{1}

1

1

2

12

{2}

1

12

3

12:,2:,:

{3}

0

0

4

12:2,2:2,:2

{4}

0

0

5

2

{2,4}

1

2

6

12:23,2:23,:23,23,3

{5}

2

26

7

12:234,2:234,:234,234,34,4

{6}

3

272

image

```//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
//#define LOCAL
typedef long long ll;
const int maxn = 1e6+5, SZ = 11, MOD = 1e9+7;
int n, indeg[maxn<<2], tindeg[maxn<<2];
char s[maxn<<1];
struct SamNode
{
int shortest, longest;
ll sum, validnum;
}sam[maxn<<2];

int newnode(int shortest, int longest, int *trans, int slink)
{
sam[n].shortest = shortest;
sam[n].longest = longest;
trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int));
return n++;
}

int insert(char ch, int u)
{
int c = ch ^ 48;
int z = newnode(-1, sam[u].longest+1, 0, -1);
int v = u;
while(~v && !~sam[v].trans[c])
{
sam[v].trans[c] = z;
}
if (!~v)
{
sam[z].shortest = 1;
return z;
}
int x = sam[v].trans[c];
if (sam[v].longest+1 == sam[x].longest)
{
sam[z].shortest = sam[x].longest + 1;
return z;
}
int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink);
sam[x].shortest = sam[z].shortest = sam[y].longest + 1;
while(~v && sam[v].trans[c] == x)
{
sam[v].trans[c] = y;
}
return z;
}

ll topsort()
{
stack<int> stk;
stk.push(0);
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (int i = 0, to;i<SZ; i++)
{
to = sam[top].trans[i];
if (!~to)
{
continue;
}
if (i ^ SZ - 1) // 不能用带 ":" 的弧转移过来
{
sam[to].sum += (sam[top].sum<<3)+(sam[top].sum<<1) + sam[top].validnum*i;
sam[to].sum %= MOD;
}
if (!--indeg[to])
{
stk.push(to);
}
}
}
ll ans = 0;
for (int i = 1;i<n; i++)
{
ans += sam[i].sum;
ans %= MOD;
}
return ans;
}

void topsort1() // 求出0到达每个节点不经过":"的弧的方法数
{
for (int i = 0;i<n; i++)
{
for (int j = 0; j<SZ; j++)
{
++indeg[sam[i].trans[j]];
}
}
memcpy(tindeg, indeg, sizeof(indeg));
stack<int> stk;
stk.push(0);
sam[0].validnum = 1;
while(!stk.empty())
{
int top = stk.top();
stk.pop();
for (int i = 0, to; i<SZ; i++)
{
to = sam[top].trans[i];
if (!~to)
{
continue;
}
if (i ^ SZ-1) // 不能用带 ":" 的弧转移过来
{
sam[to].validnum += sam[top].validnum;
}
if (!--tindeg[to])
{
stk.push(to);
}
}
}
}

ll kk()
{
int u = newnode(0,0,0,-1), i = 1;
while(s[i])
{
u = insert(s[i], u);
++i;
}
topsort1();
}

int main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
ll ans = 0;
int kase, i = 1, len;
scanf("%d", &kase);
while(kase--)
{
scanf("%s", s+i);
len = strlen(s+i);
if (kase)
{
s[i+len] = ':';
}
i += len+1;
}
printf("%lld", kk());
return 0;
}```

ac情况

`Accepted`

### 参考

【1】《史上全网最清晰后缀自动机学习 (一) 基本概念入门》

【2】《史上全网最清晰后缀自动机学习 (二) 后缀自动机的线性时间构造算法》

【3】《史上全网最清晰后缀自动机学习 (三) 后缀自动机里的树结构》

0 条评论

• ### 牛客小白月赛11D（分治、RMQ）

定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。

• ### leetcode题解 | 78. 子集

这个题目很容易想到使用DFS的方式来解决，因为组合的题容易产生转移方程，这样也是没有什么问题的。

• ### HDU6370：Werewolf 推理+拓扑排序 2018第六场杭电多校

"The Werewolves" is a popular card game among young people.In the basic game, th...

• ### 堆与栈区别

堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层...

• ### 小根堆的Java实现

堆是完全二叉树的数组形式，由于堆没有指针指向，所以可以利用下标来模拟指向，假设 i 为父节点，那么 2i+1 为左孩子，2i+2 为右孩子。假设 i 为当前节点...

LCT是一种解决动态树问题的方法，由tarjan(为什么又是他)在1982年提出，最原始的论文在这里,在论文中，tarjan除了介绍了均摊复杂度为\$O(log^...

• ### L2-006. 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

• ### 7617:输出前k大的数

7617:输出前k大的数 查看 提交 统计 提问 总时间限制:10000ms单个测试点时间限制:1000ms内存限制:65536kB描述 给定一个数组，统计前k...