4032: [HEOI2015]最短不公共子串 Time Limit: 10 Sec Memory Limit: 256 MB Submit: 507 Solved: 253 [Submit][Status][Discuss] 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
Source
【分析】 1在SAM上跑 2做一个暴力贪心 3在SAM上dp 4做一个机智的dp
（板子敲错一次Orz）
【代码】
//bzoj #include<cstdio> #include<cstring> #include<iostream> #define inf 1e9+7 #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=4005; char a[mxn],b[mxn]; int dp[mxn],next[mxn][30]; int step[mxn],pre[mxn],son[mxn][30],last[30]; int n,m,T,p,q,np,nq,ans,tot,lena,lenb,root; inline void sam() { int i,j; scanf("%s%s",a+1,b+1); lena=strlen(a+1); lenb=strlen(b+1); np=tot=root=1; fo(i,1,lenb) { int c=b[i]-'a'+1; p=np; step[np=(++tot)]=step[p]+1; while(p && !son[p][c]) son[p][c]=np,p=pre[p]; if(!p) { pre[np]=root; continue; } q=son[p][c]; if(step[q]==step[p]+1) pre[np]=q; else { step[nq=(++tot)]=step[p]+1; memcpy(son[nq],son[q],sizeof son[q]); pre[nq]=pre[q]; pre[q]=pre[np]=nq; while(p && son[p][c]==q) son[p][c]=nq,p=pre[p]; } } } inline int find(int st) { int i,j,now=1,cnt=1; fo(i,st,lena) { int c=a[i]-'a'+1; if(son[now][c]) now=son[now][c],cnt++; else return cnt; } return inf; } inline void solve1() { int i,j,ans=inf; fo(i,1,lena) ans=min(ans,find(i)); printf("%d\n",ans<inf?ans:-1); } inline void solve2() { int i,j,ans=inf; fo(i,1,lena) { int now=1; fo(j,i,lena) { while(b[now]!=a[j] && now<=lenb) now++;now++; if(now>lenb+1) {ans=min(ans,j-i+1);break;} } } printf("%d\n",ans<inf?ans:-1); } inline void solve3() { int i,j,k,ans=inf; memset(dp,0x3f,sizeof dp); dp[1]=0; fo(i,1,lena) fo(j,1,tot) dp[son[j][a[i]-'a'+1]]=min(dp[son[j][a[i]-'a'+1]],dp[j]+1); printf("%d\n",dp[0]<inf?dp[0]:-1); } inline void solve4() { int i,j; memset(dp,0x3f,sizeof dp); fo(i,1,26) last[i]=lenb+1; for(i=lenb;i;i--) { fo(j,1,26) next[i][j]=last[j]; last[b[i]-'a'+1]=i; } fo(i,1,26) next[0][i]=last[i]; dp[0]=0; fo(i,1,lena) for(j=lenb;j>=0;j--) dp[next[j][a[i]-'a'+1]]=min(dp[next[j][a[i]-'a'+1]],dp[j]+1); printf("%d\n",dp[lenb+1]<inf?dp[lenb+1]:-1); } int main() { sam(); solve1(); solve2(); solve3(); solve4(); return 0; } /* bbbb aababb */