Suffix Automation 后缀自动机

January 21, 2013

前言
完成如下概念的认识：自动机，状态，转移函数。这些都是相关的理论，可以参看黑书或者算法导论等。

分析

  1. Reg(s) 表示s这个状态能够接受的字符串的集合。
  2. Right(s) 如果a在S[l, r)出现，则它能够识别从r开始的后缀。
    Right(s) 是一个集合，表示所有S[l, r)中的r。
    有了Right(s)，只要给出字符串长度len，就能确定所有串。
    len一定是一个区间，我们称之为[Min(s), Max(s)]。
  3. 可以证明 Right(s) 只有独立和包含关系（这就证明了总复杂度是O(n)）的。
  4. Right就构成了一棵树，令Parent(s)表示其祖先，称这棵树为Parent树，Parent(s)表示包含s状态的Right集合且最小的状态。
  5. 为什么Min(s) – 1不行？ 因为出现位置超过了Right(s)了。那么Max(Parent(s)) = Min(s) – 1。
  6. 考虑转移f(s, c) = t，那么由于多了一个字符c，s的Right集合中，只有S[ri] = c才能符合条件。
    所以t的Right集合是 {r_i+1 | s[r_i] == c}。
    而且有一个显然的推论：Max(t) > Max(s)。
  7. 令fa = Parent(s)，若s有出发标号为x的边，那么fa也有，且Right(f(s, c)) 包含于 Right(f(fa, c))。

构造

  1. 这是一个在线构造法。
  2. 设源串是T，新字符是x，则新串是Tx。
  3. 考虑Right集合中包含Len(T)的集合，v1, v2, …, vk
    必然存在一个Right(p) = {L} 的节点p(f(T))，那么v1, v2, …, vk都可以用Parent函数找到。
  4. 构造新状态Right(np) = {L+1}
  5. 不妨我们假设v1 = p, v2 = Parent(v1), …, vk = root。
    考虑一个v的集合Right = {r1, r2, …, rn = L}，
    如果在它后面加字符x的话，新状态nv只有s[ri] = x才满足。
    我们知道，如果vi没有出发指向x的边，那么就没有这样的ri。
    而我们又知道，如果vi有x的边，那么所有vi+1也有。
  6. 对于没有到x的边的，连一条到np的边。
  7. 令vp是第一个有x边的状态。考虑其集合Right(vp) = {r1, r2, r3, …, rn}。
    令q = f(vp, x)，
    如果Max(q) 恰好等于 Max(vp) + 1，那么直接把Parent(np)设为q；
    否则，就说明会新建点，我们新建点nq，Right(nq) = Right(q) ∪ {L+1}，
    则，Parent(q) = nq（q是nq的真子集），
    并且Parent(np) = nq，
    由于区间包含等等等关系可以证明Parent(nq) = Parent(q)。
  8. 由于转移的时候结束位置是不起作用的，所以f(nq, *) = f(q, *)。
    最后，我们需要把所有f(vi, x) = q的点全部指向nq。

代码

const int MaxNode = 10000;
const int MaxChar = 30;

int go[MaxNode][MaxChar];
int val[MaxNode], pnt[MaxNode];
int chr[MaxNode];
int init, last, tot;

inline void init_automachine(void) {
	last = init = tot = 1;
}

void extend_automachine(int c) {
	int p = last, np = ++tot;
	val[np] = val[p] + 1; chr[np] = c;
	while (p && go[p][c] == 0)
		go[p][c] = np, p = pnt[p];

	if (p == 0)
		pnt[np] = init;
	else {
		int q = go[p][c];
		if (val[p] + 1 == val[q])
			pnt[np] = q;
		else {
			int nq = ++tot;
			val[nq] = val[p] + 1; chr[nq] = c;
			for (int j = 0; j < MaxChar; ++j)
				go[nq][j] = go[q][j];

			pnt[nq] = pnt[q], pnt[q] = nq, pnt[np] = nq;
			while (p && go[p][c] == q)
				go[p][c] = nq, p = pnt[p];
		}
	}

	last = np;
}

int main(void) {
	freopen("suffix_automachine.in", "r", stdin);
	freopen("output.txt", "w", stdout);

	int T;
	scanf("%dn", &T);

	char s[10000], t[10000];
	for (int i = 0; i < T; ++i) {
		gets(s), gets(t);

		int n = strlen(s), m = strlen(t);
		init_automachine();
		for (int i = 0; i < n; ++i)
			extend_automachine(s[i] - 'a');

		int ans = m;
		for (int i = 0, cur = init; i < m; ++i)
			if (go[cur][t[i] - 'a'] != 0)
				cur = go[cur][t[i] - 'a'];
			else {
				ans = i;
				break;
			}
		cout << ans << endl;
	}

	return 0;
}