Description：

给两个小写字母串 $A$ ， $B$ ，计算：

$(1)$ $A$ 的一个最短的子串，它不是 $B$ 的子串

$(2)$ $A$ 的一个最短的子串，它不是 $B$ 的子序列

$(3)$ $A$ 的一个最短的子序列，它不是 $B$ 的子串

$(4)$ $A$ 的一个最短的子序列，它不是 $B$ 的子序列

$1\le|A|,|B|\le 2000$

Solution：

把 $A$ 和 $B$ 的后缀自动机和子序列自动机建出来，对每个询问在 $A$ 的自动机上 $BFS$ ，在 $B$ 的自动机上对应跑，跑到 $A$ 有转移 $B$ 没转移即可，注意这样会超时，需要两个优化，一是对于已经经过的 $(a,b)$ ，可以不用再走，但不能只判 $A$ 自动机上的状态，因为 $A$ 上相同状态时 $B$ 上的指针可能在不同位置，还有就是把剪枝放在把状态压到队列之前剪掉，速度快 $2/3$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

#define MAXL 2010

struct suffix_automaton

{

	struct node

	{

		int tr[26],maxl,par;

	}s[MAXL << 1];

	int root,last,ptr;

	suffix_automaton(){root = last = ptr = 1;}

	int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

	void extend(int k)

	{

		int p = last;

		int np = newnode(s[p].maxl + 1);

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

	void build(char c[])

	{

		int l = strlen(c + 1);

		for(int i = 1;i <= l;++i)extend(c[i] - 'a');

	}

}suf1,suf2;

struct subseq_automaton

{

	struct node

	{

		int tr[26];

	}s[MAXL];

	int root;

	subseq_automaton(){root = 1;} 

	void build(char c[])

	{

		int l = strlen(c + 1);

		for(int i = 0;i <= l;++i)

		{

			for(int j = i + 1;j <= l;++j)

			{

				if(s[i + 1].tr[c[j] - 'a'] == 0)s[i + 1].tr[c[j] - 'a'] = j + 1;

			}

		}

		return;

	}

}seq1,seq2;

char a[MAXL],b[MAXL];

#define fi first

#define se second

#define mp(a,b) make_pair(a,b)

#define piii pair<int, pair<int,int> >

bool vis[MAXL << 1][MAXL << 1];

int bfs1()

{

	memset(vis,false,sizeof(vis));

	int a = suf1.root,b = suf2.root;

	queue< piii > q;

	q.push(mp(0,mp(a,b)));

	while(!q.empty())

	{

		piii k = q.front();q.pop();

		if(vis[k.se.fi][k.se.se])continue;

		vis[k.se.fi][k.se.se] = true;

		for(int i = 0;i < 26;++i)

		{

			if(suf1.s[k.se.fi].tr[i] == 0)continue;

			if(suf2.s[k.se.se].tr[i] == 0)return k.fi + 1;

			q.push(mp(k.fi + 1,mp(suf1.s[k.se.fi].tr[i],suf2.s[k.se.se].tr[i])));

		}

	}

	return -1;

}

int bfs2()

{

	memset(vis,false,sizeof(vis));

	int a = suf1.root,b = seq2.root;

	queue< piii > q;

	q.push(mp(0,mp(a,b)));

	while(!q.empty())

	{

		piii k = q.front();q.pop();

		if(vis[k.se.fi][k.se.se])continue;

		vis[k.se.fi][k.se.se] = true;

		for(int i = 0;i < 26;++i)

		{

			if(suf1.s[k.se.fi].tr[i] == 0)continue;

			if(seq2.s[k.se.se].tr[i] == 0)return k.fi + 1;

			q.push(mp(k.fi + 1,mp(suf1.s[k.se.fi].tr[i],seq2.s[k.se.se].tr[i])));

		}

	}

	return -1;

}

int bfs3()

{

	memset(vis,false,sizeof(vis));

	int a = seq1.root,b = suf2.root;

	queue< piii > q;

	q.push(mp(0,mp(a,b)));

	while(!q.empty())

	{

		piii k = q.front();q.pop();

		if(vis[k.se.fi][k.se.se])continue;

		vis[k.se.fi][k.se.se] = true;

		for(int i = 0;i < 26;++i)

		{

			if(seq1.s[k.se.fi].tr[i] == 0)continue;

			if(suf2.s[k.se.se].tr[i] == 0)return k.fi + 1;

			q.push(mp(k.fi + 1,mp(seq1.s[k.se.fi].tr[i],suf2.s[k.se.se].tr[i])));

		}

	}

	return -1;

}

int bfs4()

{

	memset(vis,false,sizeof(vis));

	queue< piii > q;

	q.push(mp(0,mp(seq1.root,seq2.root)));

	while(!q.empty())

	{

		piii k = q.front();q.pop();

		if(vis[k.se.fi][k.se.se])continue;

		vis[k.se.fi][k.se.se] = true;

		for(int i = 0;i < 26;++i)

		{

			if(seq1.s[k.se.fi].tr[i] == 0)continue;

			if(seq2.s[k.se.se].tr[i] == 0)return k.fi + 1;

			q.push(mp(k.fi + 1,mp(seq1.s[k.se.fi].tr[i],seq2.s[k.se.se].tr[i])));

		}

	}

	return -1;

}

int main()

{

	scanf("%s%s",a + 1,b + 1);

	suf1.build(a);suf2.build(b);

	seq1.build(a);seq2.build(b);

	printf("%d\n%d\n%d\n%d\n",bfs1(),bfs2(),bfs3(),bfs4());

	return 0;

}