在这里插入图片描述
UVA1673
这道题可以用广义后缀自动机，不过陈锋老师给我们讲了一个巧妙地方法，使得这道题可以用普通的后缀自动机做。
题目大意：
给出$N$个完全由数字组成的字符串。计算将这个$N$的字符串的所有子串转换为整数后先去重再求和的结果，输出其模2012的余数。也就是求其子串的所有本质不同的字符串的和。
预处理：
首先，我们可以将$N$个字符串拼接起来，拼接的部位可以用一个特殊的分隔符隔开。比如这里我用 ==:==，因为$’:’-‘0’=10$。我们将拼接好的字符串记作$S$，这样问题就转换成求$S$中所有不含分隔符的本质不同的子串的和。对$S$建立后缀自动机。
定义：
$Cnt[v]$为从$SAM$的初始状态到状态$v$中的所有不含分隔符以及前导0的数量（根据题意，前导0去掉后算一个。比如01和1算作同一个子串）。
$Sum[v]$为从初始状态到状态$v$的所有合法路径形成的数字之和。
转移方程：

即v由u转移而来。而关于合法转移，只要在转移时不向分隔符的方向走子串就不会出现分隔符；只要不再初始状态往0走，就不会出现前导0。

即当前的状态和为上一状态十进制进一位加上当前选择的路径对应的合法路径数量。
转移方式：
怎样保证方程中的$u$在$v$之前就更新过了呢？不难发现，由于$v$都是由$u$向下走一步得来，因此有：$len(u)<len(v)$因此我们将所有状态按$len$排个序，从小到大更新即可。本题中的$len$是连续且大量重复的，可以采用计数排序$O(N)$解决，不过快排也够了。
*AC代码：

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
const int MAXN = 120000;
int n;
string S;
struct SAM {
	int size, last;
	struct Node {
		int len = 0, link = 0;
		int next[11];
		void clear() {
			len = link = 0;
			memset(next, 0, sizeof(next));
		}
	} node[MAXN * 2];
	void init() {
		for (int i = 0; i < size; i++) {
			node[i].clear();
		}
		node[0].link = -1;
		size = 1;
		last = 0;
	}
	void insert(char x) {
		int ch = x - '0';
		int cur = size++;
		node[cur].len = node[last].len + 1;
		int p = last;
		while (p != -1 && !node[p].next[ch]) {
			node[p].next[ch] = cur;
			p = node[p].link;
		}
		if (p == -1) {
			node[cur].link = 0;
		}
		else {
			int q = node[p].next[ch];
			if (node[p].len + 1 == node[q].len) {
				node[cur].link = q;
			}
			else {
				int clone = size++;
				node[clone] = node[q];
				node[clone].len = node[p].len + 1;
				while (p != -1 && node[p].next[ch] == q) {
					node[p].next[ch] = clone;
					p = node[p].link;
				}
				node[q].link = node[cur].link = clone;
			}
		}
		last = cur;
	}
}sam;
int N, Size = 0;
int
Cnt[2 * MAXN],
SUM[2 * MAXN],
Order[2 * MAXN];

bool Input() {
	if (scanf("%d", &N) == EOF) {
		return false;
	}
	S.clear();
	while (N--) {
		string Temp;
		cin >> Temp;
		S.insert(S.end(), Temp.begin(), Temp.end());
		S.push_back(':');
	}

	sam.init();
	for (int i = 0; i < S.size(); ++i) {
		sam.insert(S[i]);
	}

	return true;
}
constexpr static int mod = 2012;
int DP() {
	for (int i = 0; i < sam.size; ++i) {
		Order[i] = i;
	}
	//排序
	sort(Order, Order + sam.size, [](const int&Left,const int&Right)->bool {
		return sam.node[Left].len < sam.node[Right].len;
		}
	);
	//空串合法
	Cnt[0] = 1;
	int&& Ans = 0;
	for (int i = 0; i < sam.size; ++i) {
		const int& u = Order[i];
		//如果j是初始状态，就不能往0走，否则就可以，这样就可以去除前导0
		for (int j = (u ? 0 : 1); j < 10; ++j) {
			const int& v = sam.node[u].next[j];
			if (sam.node[v].len) {
				Cnt[v] += Cnt[u];
				Cnt[v] %= mod;
				SUM[v] += SUM[u] * 10 + j * Cnt[u];
				SUM[v] %= mod;
			}
		}
		Ans += SUM[u];
		Ans %= mod;
	}
	return Ans;
}
int main() {
	while (Input()) {
		memset(Cnt, 0x0, sizeof(Cnt));
		memset(SUM, 0x0, sizeof(SUM));
		printf("%d\n", DP());
	}
	return 0;
}