记录编号	165101	评测结果	AAAAAAAAAA
题目名称	[HEOI 2015]最短不公共子串	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.718 s
提交时间	2015-06-10 10:19:08	内存使用	62.51 MiB

// Orz ztx
// Orz ztx
// Orz ztx
// The important thing need say 3 times

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int kSZC = 26;
const int kN = 2000+10;
const int kS = 4000+10;
const int INF = 1e9;
char str_a[kN], str_b[kN];
int a_len, b_len;

struct Node {
	int len, link;
	int nxt[kSZC];
}A[kS], B[kS];
int node_cnt;

int Insert(int last, int c, Node t[]) {
	int cur = ++node_cnt;
	t[cur].len = t[last].len+1;
	for (int p = last; p != -1; p = t[p].link) {
		if (!t[p].nxt[c]) {
			t[p].nxt[c] = cur;
		} else {
			int q = t[p].nxt[c];
			if (t[p].len+1 == t[q].len) {
				t[cur].link = q;
			} else {
				int clone = ++node_cnt;
				t[clone] = t[q];
				t[clone].len = t[p].len+1;
				for (int tp = p; tp != -1 && t[tp].nxt[c] == q; tp = t[tp].link) {
					t[tp].nxt[c] = clone;
				}
				t[q].link = t[cur].link = clone;
			}
			break;
		}
	}
	return cur;
}

void BuildSam(char str[], int n, Node t[]) {
	node_cnt = 0;
	memset(t, 0, sizeof(Node)*kS);
	
	t[0].link = -1;
	int last = 0;
	for (int i = 1; i <= n; i++) {
		last = Insert(last, str[i]-'a', t);
	}
}

void BuildTrans(char str[], int n, Node t[]) {
	memset(t, 0, sizeof(Node)*kS);
	for (int i = n-1; i >= 1; i--) {
		int c = str[i+1]-'a';
		for (int j = 0; j < kSZC; j++) {
			if (j == c) {
				t[i].nxt[j] = i+1;
			} else {
				t[i].nxt[j] = t[i+1].nxt[j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int c = str[i] - 'a';
		if (!t[0].nxt[c]) {
			t[0].nxt[c] = i;
		}
	}
}

int d[kS][kS];
int Solve() {
	for (int i = 0; i < kS; i++) for (int j = 0; j < kS; j++) d[i][j] = INF;
	queue<pair<int, int> > q;
	d[0][0] = 0;
	q.push(make_pair(0, 0));
	while (q.size()) {
		int l = q.front().first, r = q.front().second;
		q.pop();
		for (int c = 0; c < kSZC; c++) {
			int tl = A[l].nxt[c];
			int tr = B[r].nxt[c];
			if (tl && !tr) return d[l][r]+1;
			if (tl && d[tl][tr] > d[l][r]+1) {
				d[tl][tr] = d[l][r]+1;
				q.push(make_pair(tl, tr));
			}
		}
	}
	return -1;
}

int main() {
	//freopen("in.txt", "r", stdin);
	freopen("sus.in", "r", stdin);
	freopen("sus.out", "w", stdout);
	scanf("%s %s", str_a+1, str_b+1);
	a_len = strlen(str_a+1);
	b_len = strlen(str_b+1);
	int ans1, ans2, ans3, ans4;
	
	BuildSam(str_a, a_len, A);
	BuildSam(str_b, b_len, B);
	ans1 = Solve();
	
	BuildTrans(str_b, b_len, B);
	ans2 = Solve();
	
	BuildTrans(str_a, a_len, A);
	ans4 = Solve();
	
	BuildSam(str_b, b_len, B);
	ans3 = Solve();
	
	printf("%d\n%d\n%d\n%d\n", ans1, ans2, ans3, ans4);
	return 0;
}