【题解】跟 上一题简直一模一样

换一下bfs而已

# include <stdio.h>
# include <string.h>
# include <queue>
# include <vector>
using namespace std;

const int M=4010, Ms=26;
struct AM {
	int tot, ch[M][Ms], root;
};

struct SeqAM: public AM {
	int head[Ms], next[M];
	SeqAM() {
		tot = root = 1;
		for (int i=0; i<Ms; ++i) head[i] = tot;
	}
	inline void insert(char c) {
		++tot;
		next[tot]=head[c];
		for (int i=0; i<Ms; ++i)
			for (int j=head[i]; j&&!ch[j][c]; j=next[j]) ch[j][c]=tot;
		head[c]=tot;
	}
}SEA, SEB;

struct SufAM: public AM {
	int fail[M], len[M], cl, last;
	SufAM() {
		last=tot=root=1, cl=0;
	}
	inline void insert(char c) {
		++tot, ++cl;
		int x=tot, p=last;
		last=x, len[x] = cl;
		for (;p && !ch[p][c]; p=fail[p]) ch[p][c] = x;
		if(!p) fail[x] = root;
		else if(len[ch[p][c]] == len[p]+1) fail[x] = ch[p][c];
		else {
			int child = ch[p][c], cm=++tot;
			len[cm] = len[p]+1;
			fail[cm] = fail[child];
			for (int i=0; i<Ms; ++i) ch[cm][i] = ch[child][i];
			fail[child] = fail[x] = cm;
			for (;ch[p][c] == child; p=fail[p]) ch[p][c] = cm;
		}
	}
}SUA, SUB;

int d[M][M];
queue< pair<int, int> > Q;
inline int bfs(AM &a, AM &b) {
	memset(d, 0, sizeof(d));
	while(!Q.empty()) Q.pop();
	Q.push(make_pair(a.root, b.root)); 
	d[a.root][b.root]=1;
	while(!Q.empty()) {
		int nowa = Q.front().first, nowb = Q.front().second;
		Q.pop();
		for (int j=0; j<Ms; ++j) {
			int ca = a.ch[nowa][j], cb = b.ch[nowb][j];
			if(d[ca][cb] || !ca) continue;
			if(!cb) return d[nowa][nowb];
			d[ca][cb] = d[nowa][nowb] + 1;
			Q.push(make_pair(ca, cb));
		}
	}
	return -1;
}
char A[M], B[M];

int main() {
	scanf("%s%s", A, B);
	for (int i=0; A[i]; ++i) SEA.insert(A[i]-'a'), SUA.insert(A[i]-'a');
	for (int i=0; B[i]; ++i) SEB.insert(B[i]-'a'), SUB.insert(B[i]-'a');
	int AEBE=bfs(SEA, SEB), AUBU=bfs(SUA, SUB), AEBU=bfs(SEA, SUB), AUBE=bfs(SUA, SEB);
	printf("%d\n%d\n%d\n%d\n", AUBU, AUBE, AEBU, AEBE);
	return 0;
}