NKOJ 4022（HEOI 2015）最短不公共子串（后缀自动机+序列自动机+dp）

发表于 |
字数统计: 1,168字 | 阅读时长 ≈ 6min

P4022 [HEOI2015]最短不公共子串

问题描述

在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。

一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。

下面，给两个小写字母串A，B，请你计算：

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

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

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

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

输入格式

有两行，每行一个小写字母组成的字符串，分别代表A和B。

输出格式

输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.

样例输入

aabbcc
abcabc

样例输出

2
4
2
4

提示

对于100%的数据，A和B的长度都不超过2000

此题涉及到子串和子序列，考虑后缀自动机和序列自动机。
那么此题就是在两个自动机上dp。
对于第一问，令$F1[x][y]$表示从A的后缀自动机上x节点，B的后缀自动机上y节点出发的最短不公共子串长度，那么当$x\neq0,y=0$时$F1[x][y]=0$，然后直接在两个自动机上转移就行了，$F1[x][y]=min(F1[tx][ty]+1)$
对于第二问，在A的后缀自动机和B的序列自动机上同样dp即可。
对于第三问，在A的序列自动机和B的后缀自动机上同样dp即可。
对于第四问，在A的序列自动机和B的序列自动机上同样dp即可。

复杂度$O(26n^2)?$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 4005
using namespace std;
struct PAM
{
	int tot,rt,las[26],pre[N],son[N][26];
	PAM()
	{
		tot=rt=1;
		for(int i=0;i<26;i++)las[i]=1;
	}
	void Ins(int c)
	{
		tot++;pre[tot]=las[c];
		for(int i=0;i<26;i++)
		for(int j=las[i];j&&!son[j][c];j=pre[j])son[j][c]=tot;
		las[c]=tot;
	}
}PA,PB;
struct SAM
{
	int rt,tot,las,son[N][26],Max[N],pra[N];
	SAM(){tot=las=rt=1;}
	int NP(int x)
	{
		Max[++tot]=x;
		return tot;
	}
	void Ins(int t)
	{
		int p=las,q,np,nq;
		np=NP(Max[p]+1);
		while(p&&!son[p][t])son[p][t]=np,p=pra[p];
		if(!p)pra[np]=rt;
		else
		{
			q=son[p][t];
			if(Max[q]==Max[p]+1)pra[np]=q;
			else
			{
				nq=NP(Max[p]+1);
				memcpy(son[nq],son[q],sizeof(son[q]));
				pra[nq]=pra[q];
				pra[q]=pra[np]=nq;
				while(son[p][t]==q)son[p][t]=nq,p=pra[p];
			}
		}
		las=np;
	}
}SA,SB;
char s1[N],s2[N];
int n,m,ans;
int F1[N][N],F2[N][N>>1],F3[N>>1][N],F4[N>>1][N>>1];
int DFS1(int x,int y)
{
	if(x&&y==0)return 0;
	if(!x||!y)return 1e9;
	if(F1[x][y]!=-1)return F1[x][y];
	F1[x][y]=1e9;
	for(int i=0;i<26;i++)F1[x][y]=min(F1[x][y],DFS1(SA.son[x][i],SB.son[y][i])+1);
	return F1[x][y];
}
int DFS2(int x,int y)
{
	if(x&&y==0)return 0;
	if(!x||!y)return 1e9;
	if(F2[x][y]!=-1)return F2[x][y];
	F2[x][y]=1e9;
	for(int i=0;i<26;i++)F2[x][y]=min(F2[x][y],DFS2(SA.son[x][i],PB.son[y][i])+1);
	return F2[x][y];
}
int DFS3(int x,int y)
{
	if(x&&y==0)return 0;
	if(!x||!y)return 1e9;
	if(F3[x][y]!=-1)return F3[x][y];
	F3[x][y]=1e9;
	for(int i=0;i<26;i++)F3[x][y]=min(F3[x][y],DFS3(PA.son[x][i],SB.son[y][i])+1);
	return F3[x][y];
}
int DFS4(int x,int y)
{
	if(x&&y==0)return 0;
	if(!x||!y)return 1e9;
	if(F4[x][y]!=-1)return F4[x][y];
	F4[x][y]=1e9;
	for(int i=0;i<26;i++)F4[x][y]=min(F4[x][y],DFS4(PA.son[x][i],PB.son[y][i])+1);
	return F4[x][y];
}
int main()
{
	scanf("%s%s",&s1[1],&s2[1]);
	s1[0]=s2[0]='%';
	n=strlen(s1)-1;
	m=strlen(s2)-1;
	for(int i=1;i<=n;i++)PA.Ins(s1[i]-'a'),SA.Ins(s1[i]-'a');
	for(int i=1;i<=m;i++)PB.Ins(s2[i]-'a'),SB.Ins(s2[i]-'a');
	memset(F1,-1,sizeof(F1));
	memset(F2,-1,sizeof(F2));
	memset(F3,-1,sizeof(F3));
	memset(F4,-1,sizeof(F4));
	ans=DFS1(1,1);printf("%d\n",ans==1e9?-1:ans);
	ans=DFS2(1,1);printf("%d\n",ans==1e9?-1:ans);
	ans=DFS3(1,1);printf("%d\n",ans==1e9?-1:ans);
	ans=DFS4(1,1);printf("%d\n",ans==1e9?-1:ans);
}