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

时间限制:15000ms
单点时限:3000ms
内存限制:512MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集，顾名思义，这部作品集里有许多作品，但是所有的
作品有一个共同特征：只用了十个音符，所有的音符都表示成0-9的数字。

现在小Hi想知道这部作品集中所有不同的旋律的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。答
案有可能很大，我们需要对（10^9 + 7)取摸。

解题方法提示

输入
第一行，一个整数N，表示有N部作品。

接下来N行，每行包含一个由数字0-9构成的字符串S。

所有字符串长度和不超过 1000000。

输出
共一行，一个整数，表示答案 mod （10^9 + 7)。

样例输入
2
101
09
样例输出
131

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

//#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 trans[SZ], slink;
	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;
	sam[n].slink = slink;
	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;
		v = sam[v].slink;
	}
	if (!~v)
	{
		sam[z].slink = 0;
		sam[z].shortest = 1;
		return z;
	}
	int x = sam[v].trans[c];
	if (sam[v].longest+1 == sam[x].longest)
	{
		sam[z].slink = x;
		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].slink = sam[z].slink = y;
	sam[x].shortest = sam[z].shortest = sam[y].longest + 1;
	while(~v && sam[v].trans[c] == x)
	{
		sam[v].trans[c] = y;
		v = sam[v].slink;
	}
	sam[y].shortest = sam[sam[y].slink].longest + 1;
	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();
	return topsort();
}

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;
}

Accepted