[HDOJ 4436 a.k.a 天津2012 F] 后缀自动机

【题意】

给定N个数字串,每个串的子串成一个数字,问这些数字放进一个set里面去重后和模2012是多少

【算法】
后缀数组也可以做,但是后缀自动机无疑简单一点。
类似于后缀数组,把所有串通过10这个不属于任意一个数字的元素串连在一起。
然后把结点按val直接sort一下,从前往后递推统计。
递推的时候记录两个值,到达这个结点的方案数way以及到达这个状态的数字之和sum。
每次接收一个c转移显然就应该是给下一个结点的sum加上$$\sum_{i = 1}^{way} (number_i * 10 + c)$$。
把这个式子的常数c拉出来就是$$way * c + 10 * \sum_{i = 1}^{way} number_i$$
亦即$$way * c + 10 * sum$$
就这样从前往后推一下就好了,最后把每个结点的sum值都加起来就是答案。
推的时候要注意的就只有两点

  1. 根节点不应该接收0开头的串,因为这会弄出有前导0的串从而导致重复,这个很显然吧。
  2. 所有的转移都无视10这个分支,因为那本身就是不应该走的…这个也很显然把。

【时间复杂度】
$$O(N * 11 + N \log N)$$
其中N为输入字符总数。后面的N lg N是因为我贪方便直接按val sort了,这一步用了链表跳一下很容易做到O(n)的。 11自然就是字符集大小了。
【空间复杂度】
$$O(N * 11)$$
【吐槽】
今天贴了后缀自动机的模板以后花了不到5分钟就过掉了…现场调了1小时没过是怎么回事,当时的做法是一模一样的 :Cry-Out: 难道又是模板敲错了?
好后悔没有把现场打印的代码拿回来。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 250005;
const int Mod = 2012;
 
struct Node {
	Node *ch[11], *fa;
	int val;
	int way;
	int sum;
	Node(): 
		val(0), fa(NULL), way(0), sum(0) { 
		memset(ch, 0, sizeof(ch));
	}
}pool[N * 2 + 5], *last, *root;
vector <Node *> vec[N];
 
namespace SAM {
	int cnt;
 
	void init() {
		if (cnt)
			for (int i = 0; i < cnt; i++)
				pool[i] = Node();
		cnt = 1;
		root = &pool[0];
		last = root;
	}
 
	void add(int c) {
		Node *p = last, *np = &pool[cnt++];
		last = np;
		np->val = p->val + 1;
		for  (; p && !p->ch[c]; p = p->fa)
			p->ch[c] = np;
		if (!p) {
			np->fa = root;
		} else {
			Node *q = p->ch[c];
			if (p->val + 1 == q->val) {
				 np->fa = q;
			} else {
				Node *nq = &pool[cnt++];
				*nq = *q;
				nq->val = p->val + 1;
				q->fa = nq;
				np->fa = nq;
				for (; p && p->ch[c] == q; p = p->fa)
					p->ch[c] = nq;
			}
		}
	}
}
 
bool cmp(int i, int j) {
	return pool[i].val < pool[j].val;
}
 
int n, m;
char S[N], buf[N];
 
void calc() {
	int ans = 0;
	vector <int> vec;
	for (int i = 0; i < SAM::cnt; i++) {
		vec.push_back(i);
		pool[i].way = pool[i].sum = 0;
	}
	sort(vec.begin(), vec.end(), cmp);
	root->way = 1;
	root->sum = 0;
	foreach (it, vec) {
		int i = *it;
		Node *p = &pool[i];
		for (int c = i == 0 ? 1 : 0; c < 10; c++) {
			if (p->ch[c]) {
				p->ch[c]->way += p->way;
				p->ch[c]->way %= Mod;
				p->ch[c]->sum += p->sum * 10 + p->way * c;
				p->ch[c]->sum %= Mod;
			}
		}
		ans += p->sum;
		ans %= Mod;
	}
	printf("%d\n", ans);
}
 
int main(){
	while (scanf("%d", &n) != EOF) {
		m = 0;
		SAM::init();
		for (int i = 0; i < n; i++) {
			scanf("%s", buf);
			int len = strlen(buf);
			for (int j = 0; j < len; j++) {
				SAM::add(buf[j] - '0');
			}
			SAM::add(10);
		}
		calc();
	}
}

[HDOJ 4436 a.k.a 天津2012 F] 后缀自动机》上有1条评论

  1. Pingback引用通告: 2012 ACM/ICPC 天津赛区现场赛解题报告汇总 - ACM/ICPC信息站

发表评论

电子邮件地址不会被公开。