bzoj 4032 [HEOI2015]最短不公共子串

bzoj 4032 [HEOI2015]最短不公共子串

​​ Description

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

一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。 一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。 下面，给两个小写字母串A，B，请你计算： (1) A的一个最短的子串，它不是B的子串 (2) A的一个最短的子串，它不是B的子序列 (3) A的一个最短的子序列，它不是B的子串 (4) A的一个最短的子序列，它不是B的子序列 Input

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

Output

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

Sample Input

aabbcc abcabc Sample Output

2 4 2 4 HINT

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

我好菜..

orz题解​​n^2枚举所有a的后缀然后最长公共后缀+1即是答案

第二问 枚举在A中的起点然后 设转移数组nxt 贪心转移即可 尽量多匹配 使得 当前起点的A以后不可能满足答案

第三问 对B 建SAM 然后n^2递推dp 表示dp[i][j]当前在i位置 在SAM上j位置的最短匹配 然后如果不匹配了+1即可

第四问 同第三问但需要加入贪心转移即可 使得当前A结尾的序列于B开头的后缀序列尽可能匹配 如果不匹配了就一定是答案

#include #include#includeusing namespace std;const int N=2200;const int inf=0x3f3f3f3f;int last=1,cnt=1,root=1;int fa[N<<1],ch[N<<1][26],len[N<<1],a[N],b[N],nxt[N][26],n,m,lst[N],dp[N][N],dp1[N<<1],ans;char s1[N],s2[N]; inline void insert1(int x){ int p=last,np=++cnt;len[np]=len[p]+1; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{ int q=ch[p][x];if (len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[q]=fa[np]=nq; len[nq]=len[p]+1;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;}int main(){ freopen("bzoj4032.in","r",stdin); scanf("%s",s1+1);scanf("%s",s2+1); n=strlen(s1+1);m=strlen(s2+1);ans=inf; for (int i=1;i<=n;++i) a[i]=s1[i]-'a'; for (int i=1;i<=m;++i) b[i]=s2[i]-'a'; for (int i=0;i<26;++i) lst[i]=m+1; for (int i=m;~i;--i){ for (int j=0;j<26;++j) nxt[i][j]=lst[j];lst[b[i]]=i; } for (int i=n;i;--i) for (int j=m;j;--j) if (a[i]==b[j]) dp[i][j]=dp[i+1][j+1]+1; for (int i=1;i<=n;++i){static int ans1;ans1=0; for (int j=1;j<=m;++j) ans1=max(ans1,dp[i][j]); if (ans1!=n-i+1) ans=min(ans,ans1+1); }printf("%d\n",ans==inf?-1:ans);ans=inf; for (int i=1,now;i<=n;++i){now=0; for (int j=i;j<=n;++j){ int y=nxt[now][a[j]]; if (y>m){ans=min(j-i+1,ans);break;}now=nxt[now][a[j]]; } } printf("%d\n",ans==inf?-1:ans); memset(dp1,0x3f,sizeof(dp1));dp1[1]=0;ans=inf; for (int i=1;i<=m;++i) insert1(b[i]); for (int i=1;i<=n;++i) for (int j=1,y;j<=cnt;++j){ y=ch[j][a[i]]; if (!y) ans=min(ans,dp1[j]+1);else dp1[y]=min(dp1[y],dp1[j]+1); } printf("%d\n",ans==inf?-1:ans); memset(dp1,0x3f,sizeof(dp1));dp1[0]=0;ans=inf; for (int i=1;i<=n;++i){ for (int j=m;~j;--j){ int y=nxt[j][a[i]]; if (y>m) ans=min(ans,dp1[j]+1);else dp1[y]=min(dp1[j]+1,dp1[y]); } }printf("%d\n",ans==inf?-1:ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。