Category: Computer Science

本Tag来源于我与Freda同学的一段日常对话，我问她，这事儿，你知道吗？

题材敬告：本文的内容多涉及人工智能，神经网络，计算语言学。

(2020-04-07) 三段论（人是会死的；苏格拉底是人；苏格拉底会死）的英文是Syllogism.

(2018-06-05) #你知道吗#1：\(\tanh(x)\)的导数是\(1 – \tanh^2(x)\)。因此在神经网络优化中使用\(\tanh\)做激活函数可以在反向传播时计算非常高效。

(2018-06-05) #你知道吗#2：\(\tanh(x) = 2 \sigma(2x) – 1\)，其中\(\sigma\)是Sigmoid函数。

(2018-06-05) #你知道吗#3：Distributional Vector和Distributed Vector是不同的两个概念：Distributional是指真·PMI矩阵，而Distributed指的是Word2Vec等模型。当然Levy et.al. 的paper证明了两者的（在一定条件下的）等价性。

(2018-06-11) #你知道吗#4：数词不止有One, Two, Three那么简单。Quoted from wiki:

Numerals are often conflated with other parts of speech: nouns (cardinal numerals, e.g., “one”, and collective numerals, e.g., “dozen”), adjectives (ordinal numerals, e.g., “first”, and multiplier numerals, e.g., “single”) and adverbs (multiplicative numerals, e.g., “once”, and distributive numerals, e.g., “singly”).

(2018-10-02) #你知道吗#5：Language Model中最常用的评价指标之一Perplexity的发明者是Jelinek et al. 1977. “Perplexity – a measure of the difficulty of speech recognition tasks”. Cited by 171 (as of 2018-10-02).

(2018-10-26) #你知道吗#6：”a priori”和”prior”是两个（在意思上没有什么关系的）词。”a priori”合起来是一个词，形容词属性，表示“显然的”。而“prior”是名词属性，表示“先验（分布）”，一般用在Bayesian的上下文中，和“posterior”对应。另外“an a priori prior”意思是：“一个显然的先验分布”。 // 经过了长达两周的纠结，我们终于搞清楚了这两个词的意思。

(2021-02-10) #你知道吗#7：https://en.wikipedia.org/wiki/Apprenticeship_learning 的意思是”Learning from Demonstration.”

先回忆两个基本知识点。

• 母函数：就像是二项式展开，(x+y)^n，可以表示n个物品（分先后）用两种颜色染色，方案数是多少。
• Polya定理：本质上是Burnside引理的进一步延伸，其中color^c(g)，c(g)表示循环节个数，求的就是不动点的个数，可以理解为在同一个循环节中所有的元素必须染成相同颜色。

那么将两者结合在一起，考虑一个置换g。

1. 对于其中的一个长度为i的循环，染色方法用母函数表示出来就是(r^i+g^i+b^i)，原因是这i个元素必须用同一种颜色染色，因此不是(r+g+b)^i！
2. 然后考虑若干个不相交的置换，那么直接将他们母函数相乘。
3. 最后对所有置换求母函数的乘积，就可以得到答案。

例题解释。9颗珠子一个环，两种颜色染色，问6黑3白的染色方法数是多少。

• 循环：(x + y)^9 + (x^3 + y^3)^3*2 + (x^9 + y^9)*6
• 翻折：1个单元素，4个双元素，(x + y)*(x^2 + y^2)^4*9
• 最终答案：x^9 + x^8 y + 4 x^7 y^2 + 7 x^6 y^3 + 10 x^5 y^4 + 10 x^4 y^5 + 7 x^3 y^6 + 4 x^2 y^7 + x y^8 + y^9

完美解决。

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

分析

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