hdu 4436 | 2012 Asia Tianjin Regional Contest str2int (dp+后缀自动机，多串建立)
http://acm.hdu.edu.cn/showproblem.php?pid=4436
题意：
给出n个仅由数字组成的字符串，问n个字符串的所有不同子串的和。
思路：
SAM水题
从初始状态开始，走过所有路径，就是该SAM表示的所有的（不重复）子串。
因此只需要从根节点按照拓扑序（这回是根据len从小到大）转移好了。
考虑num[i]表示从SAM中的init状态到i状态能表示的子串的数量。
dp[i]表示从SAM中的init状态到i状态所表示的子串对应的和（也就是到该节点的子串的答案）
那么对于SAM中一个u->v（其中u和v是状态，设转移边为j，j属于0..9）的转移
有num[v]+=num[u]
dp[v] = dp[u] * 10 + num[u] * j
初始根节点num[rt]=1,表示唯一的空串。
需要注意，前缀0的数不考虑，所以SAM中 init状态不转移0这条边。
/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :4436.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6#define MAXALP 12
7const int mod = 2012;
8struct state
9{
10 int len, link, nxt[MAXALP];
11};
12const int N =1E5+7;
13state st[N*2];
14int sz, last,rt;
15char s[N];
16int cnt[2*N],rk[2*N];//for radix sort
17void sa_init()
18{
19 sz = 0;
20 last = rt = ++sz;
21 st[1].len = 0;
22 st[1].link=-1;
23 ms(st[1].nxt,-1);
24 ms(cnt,0);
25}
26void sa_extend(int c)
27{
28 int cur = ++sz;
29 st[cur].len = st[last].len + 1;
30 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
31 int p;
32 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
33 st[p].nxt[c] = cur;
34 if (p == -1) {
35 st[cur].link = rt;
36 } else {
37 int q = st[p].nxt[c];
38 if (st[p].len + 1 == st[q].len) {
39 st[cur].link = q;
40 } else {
41 int clone = ++sz ;
42 st[clone].len = st[p].len + 1;
43 st[clone].link = st[q].link;
44 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
45 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
46 st[p].nxt[c] = clone;
47 st[q].link = st[cur].link = clone;
48 }
49 }
50 last = cur;
51}
52int num[2*N],dp[2*N]; //num[i]表示SAM上到达状态i的子串的数量。
53//sum[i]表示SAM上到达状态i的答案。
54int n;
55int main()
56{
57#ifndef ONLINE_JUDGE
58 freopen("./in.txt","r",stdin);
59#endif
1 while (~scanf("%d",&n))
2 {
3 sa_init();
1 ms(num,0);
2 ms(dp,0);
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 scanf("%s",s+1);
6 int len_s = strlen(s+1);
7 for ( int i = 1 ; i <= len_s ; i++)
8 {
9 sa_extend(s[i]-'0');
10 }
11 sa_extend(10); //插入一个没有出现的字符做分隔符
12 }
13 // a simple radix sort
14 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
15 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
16 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
1 num[rt] = 1;
2 for ( int i = 1 ; i <= sz ; i++)
3 {
4 int u = rk[i];
5// printf("u:%d\n",u);
6 for ( int j = 0 ;j < 10 ; j++)
7 {
8 if (i==1&&j==0) continue; //有前缀0不更新答案，也就是初始态的不转移到0. i==1时表示初始态
9 int v = st[u].nxt[j];
10 if (v==-1) continue;
11 num[v] += num[u];
12 dp[v] = dp[v] + (dp[u] * 10 ) + num[u] * j; //类似数位dp,u所表示的状态左移一位，所以dp[u]*10,
13 //然后有num[u]个子串到达u，每个都可以转移j这条边，因此答案贡献是num[u]*j
14 dp[v] %=mod;
15 }
16 }
17 int ans = 0 ;
18 for ( int i = 1 ; i <= sz ; i++) ans = ( ans + dp[i])%mod;
19 printf("%d\n",ans);
20 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}