对于 100% 的数据, A 和 B 的长度都不超过 2000
真正的四合一, 一题更比四题强.
本题需要用到序列自动机和后缀自动机, 后缀自动机在这里就不赘述了, 说一下序列自动机: 序列自动机就是对于序列的每一位 $i$ 维护 $next[i][j]$ 表示在第 $i$ 个数之后最早出现 $j$ 数字的位置, 构建时只需要倒序枚举序列更新 $next$ 数组即可. 设串长为 $n$.
子任务 1
维护 $f[i][j]$ 表示以 $A$ 的第 $i$ 个字符为结尾的前缀和以 $B$ 的第 $j$ 个字符为结尾的前缀的最长公共后缀, 那么对于每个 $i$, 枚举所有的 $j$ 并取 $f[i][j]$ 的最大值 $+1$ 来更新答案. 注意当 $f[i][j]$ 的最大值等于 $i$ 时不能更新答案. 时间复杂度为 $O(n^2)$
子任务 2
对 $B$ 建序列自动机, 对于以 $A$ 的第 $i$ 个字符为开头的后缀, 我们将它在序列自动机上匹配, 当到一个位置失配时, 用当前匹配长度 $+1$ 来更新答案. 时间复杂度为 $O(n^2)$.
子任务 3
对 $B$ 建后缀自动机, 维护 $f[i]$ 表示 $A$ 的子序列匹配到后缀自动机上的 $i$ 点的最短长度. 枚举 $A$ 的每个字符来更新 $f$ 数组: 当自动机上当前点 $x$ 能匹配当前枚举字符时 $f[to]=min(f[to],f[x]+1)$, 否则用 $f[x]+1$ 来更新答案. 注意 $x$ 要倒序枚举防止更新到当前层. 时间复杂度为 $O(n^2)$.
子任务 4
与子任务 3 的做法类似, 只需要将后缀自动机换成序列自动机即可. 时间复杂度为 $O(n^2)$.
- #include<set>
- #include<map>
- #include<queue>
- #include<stack>
- #include<cmath>
- #include<cstdio>
- #include<vector>
- #include<bitset>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- int n,m;
- char S[3000];
- char T[3000];
- namespace subtask1
- {
- int f[3000][3000];
- int solve()
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)
- {
- if(S[i]==T[j])
- {
- f[i][j]=f[i-1][j-1]+1;
- }
- }
- }
- int ans=1<<30;
- for(int i=1;i<=n;i++)
- {
- int res=0;
- for(int j=1;j<=m;j++)
- {
- res=max(res,f[i][j]);
- }
- if(res!=i)
- {
- ans=min(res+1,ans);
- }
- }
- return ans>n?-1:ans;
- }
- };
- namespace subtask2
- {
- int next[3000][30];
- int suf[30];
- int solve()
- {
- for(int i=0;i<26;i++)
- {
- suf[i]=m+1;
- }
- for(int i=m;i>=0;i--)
- {
- for(int j=0;j<26;j++)
- {
- next[i][j]=suf[j];
- }
- suf[T[i]-'a']=i;
- }
- int ans=1<<30;
- for(int i=1;i<=n;i++)
- {
- int now=0;
- for(int j=i;j<=n;j++)
- {
- now=next[now][S[j]-'a'];
- if(now>m)
- {
- ans=min(ans,j-i+1);
- break;
- }
- }
- }
- return ans>n?-1:ans;
- }
- };
- namespace subtask3
- {
- int tr[5000][30];
- int len[5000];
- int pre[5000];
- int f[5000];
- int cnt=1;
- int last=1;
- void insert(int x)
- {
- int p=last;
- int np=++cnt;
- last=np;
- len[np]=len[p]+1;
- for(;p&&!tr[p][x];p=pre[p])
- {
- tr[p][x]=np;
- }
- if(!p)
- {
- pre[np]=1;
- }
- else
- {
- int q=tr[p][x];
- if(len[p]+1==len[q])
- {
- pre[np]=q;
- }
- else
- {
- int nq=++cnt;
- pre[nq]=pre[q];
- memcpy(tr[nq],tr[q],sizeof(tr[q]));
- pre[np]=pre[q]=nq;
- len[nq]=len[p]+1;
- for(;p&&tr[p][x]==q;p=pre[p])
- {
- tr[p][x]=nq;
- }
- }
- }
- }
- int solve()
- {
- for(int i=1;i<=m;i++)
- {
- insert(T[i]-'a');
- }
- memset(f,0x3f,sizeof(f));
- f[1]=0;
- int ans=1<<30;
- for(int i=1;i<=n;i++)
- {
- for(int j=cnt;j>=1;j--)
- {
- int now=tr[j][S[i]-'a'];
- if(now)
- {
- f[now]=min(f[now],f[j]+1);
- }
- else
- {
- ans=min(ans,f[j]+1);
- }
- }
- }
- return ans>n?-1:ans;
- }
- };
- namespace subtask4
- {
- int next[3000][30];
- int f[3000];
- int suf[30];
- int solve()
- {
- for(int i=0;i<26;i++)
- {
- suf[i]=m+1;
- }
- for(int i=m;i>=0;i--)
- {
- for(int j=0;j<26;j++)
- {
- next[i][j]=suf[j];
- }
- suf[T[i]-'a']=i;
- }
- memset(f,0x3f,sizeof(f));
- f[0]=0;
- int ans=1<<30;
- for(int i=1;i<=n;i++)
- {
- for(int j=m;j>=0;j--)
- {
- int now=next[j][S[i]-'a'];
- if(now>m)
- {
- ans=min(ans,f[j]+1);
- }
- else
- {
- f[now]=min(f[now],f[j]+1);
- }
- }
- }
- return ans>n?-1:ans;
- }
- };
- int main()
- {
- scanf("%s%s",S+1,T+1);
- n=strlen(S+1);
- m=strlen(T+1);
- printf("%d\n",subtask1::solve());
- printf("%d\n",subtask2::solve());
- printf("%d\n",subtask3::solve());
- printf("%d\n",subtask4::solve());
- }
来源: http://www.bubuko.com/infodetail-2996721.html