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

分析

  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;
}