这其实是道水题。。。
题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=4032
(luogu)https://www.luogu.org/problemnew/show/P4112
题解:
Task 1
\(O(n^2)\)做法无数(也有不用SAM的\(O(n^2)\)做法)，我讲一下我的做法。
直接对B串建后缀自动机，用A串在上面跑，而且是像求两个串的最长公共子串那样跑，如果遇到失配了就拿当前长度\(+1\)更新答案。但是要注意失配后当前的长度不能设成当前节点的\(len\)(最大长度)，而应该是\(len[fail[u]]+1\)(最小长度)。
时间复杂度\(O(n)\).
由于没有在网上看到\(O(n)\)做法，所以此做法正确性未知(能过，但是数据很水，一开始写成\(len\)了依然能过10个点中的9个)。
Task 2
设\(nxt[i][j]\)表示B序列中第\(i\)个位置之后最靠前的字符\(j\)的位置。枚举A子串的起始位置，贪心即可。
时间复杂度\(O(n^2)\).
听说有人把这个东西称作“序列自动机”，感觉也有道理啊，这玩意确实像个自动机。
Task 3
子串就用后缀自动机，子序列就用“序列自动机”美滋滋。
设\(dp[i][j]\)表示A串前\(i\)个位置匹配B串后缀自动机的节点\(j\)，最少用多少长度。如果能转移就转移，不能转移就用\(dp[i][j]+1\)更新答案。注意要在每个\(i\)都更新(因为子序列可以不到头)。
然后第一维可以像01背包一样省掉，我觉得第二维要按先儿子后父亲的顺序循环。但是网上有人直接从\(1\)到\(siz\)循环也能过？
注意\(dp\)数组要开两倍。
Task 4
设\(dp[i][j]\)表示A串前\(i\)个位置匹配B串前\(j\)个位置的最小长度。
转移同Task 3. 如果用一维数组，从\(n\)到\(1\)循环。
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 2000;
const int S = 26;
int len[(N<<1)+3];
int fa[(N<<1)+3];
int son[(N<<1)+3][S+3];
char a[N+3],b[N+3];
int pos[S+3];
int nxt[N+3][S+3];
int dp[(N<<1)+3];
int ord[(N<<1)+3];
int buc[N+3];
int n,m,siz,rtn,lstpos;void initSAM()
{
siz = rtn = lstpos = 1;
}void insertchar(char ch)
{
int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1;
for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}
if(!p) {fa[np] = rtn;}
else
{
int q = son[p][ch];
if(len[p]+1==len[q]) {fa[np] = q;}
else
{
siz++; int nq = siz; len[nq] = len[p]+1;
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq] = fa[q]; fa[np] = fa[q] = nq;
for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}
}
}
}void update(int &x,int y) {x = min(x,y);}int main()
{
initSAM();
scanf("%s",a+1); n = strlen(a+1); for(int i=1; i<=n; i++) a[i] -= 96;
scanf("%s",b+1); m = strlen(b+1); for(int i=1; i<=m; i++) b[i] -= 96;
for(int i=1; i<=m; i++)
{
insertchar(b[i]);
}
for(int i=1; i<=m; i++)
{
for(int j=pos[b[i]]; j<i; j++)
{
nxt[j][b[i]] = i;
}
pos[b[i]] = i;
}
for(int i=1; i<=S; i++)
{
for(int j=0; j<=m; j++) {if(!nxt[j][i]) nxt[j][i] = m+1;}
}
for(int i=1; i<=siz; i++) buc[len[i]]++;
for(int i=1; i<=n; i++) buc[i] += buc[i-1];
for(int i=siz; i>=1; i--) ord[buc[len[i]]--] = i;
//Question 1
int u = rtn,cur = 0,ans1 = m+1;
for(int i=1; i<=n; i++)
{
while(u && son[u][a[i]]==0) {ans1 = min(ans1,cur+1); u = fa[u]; cur = len[fa[u]]+1;}
if(son[u][a[i]]!=0) {cur++; u = son[u][a[i]];}
else {ans1 = 1; u = rtn; cur = 0;}
}
if(ans1==m+1) printf("-1\n");
else printf("%d\n",ans1);
//Question 2
int ans2 = n+1;
for(int i=1; i<=n; i++)
{
int j = 0;
for(int k=i; k<=n; k++)
{
if(nxt[j][a[k]]<=m)
{
j = nxt[j][a[k]];
}
else
{
ans2 = min(ans2,k-i+1);
}
}
}
if(ans2==n+1) printf("-1\n");
else printf("%d\n",ans2);
//Question 3
int ans3 = n+1;
for(int i=1; i<=siz; i++) dp[i] = n+1; dp[rtn] = 0;
for(int i=1; i<=n; i++)
{
for(int j=siz; j>=1; j--)
{
int u = ord[j];
if(son[u][a[i]])
{
update(dp[son[u][a[i]]],dp[u]+1);
}
else
{
update(ans3,dp[u]+1);
}
}
}
if(ans3==n+1) printf("-1\n");
else printf("%d\n",ans3);
//Question 4
int ans4 = n+1;
for(int i=1; i<=n; i++) dp[i] = n+1; dp[0] = 0;
for(int i=1; i<=n; i++)
{
for(int j=m; j>=0; j--)
{
if(nxt[j][a[i]]<=m)
{
update(dp[nxt[j][a[i]]],dp[j]+1);
}
else
{
update(ans4,dp[j]+1);
}
}
}
if(ans4==n+1) printf("-1\n");
else printf("%d\n",ans4);
return 0;
}
