[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: 难道又是模板敲错了？
好后悔没有把现场打印的代码拿回来。

#include 
#include 
#include 
#include 
#include 
using namespace std;

template  void checkmin(T &t,T x){if (x < t) t = x;}
template  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  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; p = p->fa)
			p->ch = np;
		if (!p) {
			np->fa = root;
		} else {
			Node *q = p->ch;
			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 == q; p = p->fa)
					p->ch = 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  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) {
				p->ch->way += p->way;
				p->ch->way %= Mod;
				p->ch->sum += p->sum * 10 + p->way * c;
				p->ch->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();
	}
}