Description

 在虐各種最長(zhǎng)公共子串、子序列的題虐的不耐煩了之后，你決定反其道而行之。

Input

有兩行，每行一個(gè)小寫(xiě)字母組成的字符串，分別代表A和B。

Output

輸出4行，每行一個(gè)整數(shù)，表示以上4個(gè)問(wèn)題的答案的長(zhǎng)度。如果沒(méi)有符合要求的答案，輸出-1.

Sample Input

Sample Output

HINT

 對(duì)于100%的數(shù)據(jù)，A和B的長(zhǎng)度都不超過(guò)2000

Source

題解：DP+后綴自動(dòng)機(jī)

四個(gè)問(wèn)題寫(xiě)了四個(gè)部分分，我也是醉了。。。

這道題的第一問(wèn)我竟然被卡hash了！！！人生第一次被卡hash。。。還是老老實(shí)實(shí)的DP吧。

其實(shí)只有第三問(wèn)需要用后綴自動(dòng)機(jī)。。。。剛開(kāi)始還死往那上面想。

四個(gè)部分的題解都在程序的注釋中，懶得再寫(xiě)一遍了

#include<iostream>  #include<cstring>  #include<algorithm>  #include<cmath>  #include<cstdio>#include<map>  #define N 20013  #define p1 2000001001#define ull unsigned long longusing namespace std;  int cnt,n,m,np,p,q,nq,l[N],r[N],pos[N],root;  int ch[N][30],fa[N],len[N],last,ch1[N][30],f[2003][2003];  ull mi[N];char s[N],s1[N];  map<int,int> mp;map<ull,int> mp1; void extend(int i)  {      int c=s1[i]-'a'+1;      p=last; np=last=++cnt; l[np]=l[p]+1;      for (;!ch[p][c]&&p;p=fa[p]) ch[p][c]=np;      if (!p) fa[np]=root;      else {          q=ch[p][c];          if (l[q]==l[p]+1) fa[np]=q;          else {              nq=++cnt; l[nq]=l[p]+1;              memcpy(ch[nq],ch[q],sizeof(ch[q]));              fa[nq]=fa[q];              fa[q]=fa[np]=nq;              for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;          }      }   }  void solve1()  {      /*mi[0]=1;	for (int i=1;i<=max(n,m)+2;i++)  mi[i]=mi[i-1]*p1;	for (int i=1;i<=m;i++){		ull x=(ull)s1[i]*mi[1]; mp1[x]=1;		//cout<<x<<endl;		for (int j=i+1;j<=m;j++) {			x=x*p1+s1[j]*mi[i]; 			mp1[x]=(j-i+1);		//	cout<<x<<endl;		}	} 	int mn=m+1;	for (int i=1;i<=n;i++) {		ull x=(ull)s[i]*mi[1];		if (!mp1[x]) mn=min(mn,1);		for (int j=i+1;j<=n;j++){			x=x*p1+s[j]*mi[1];			if (!mp1[x]&&j-i+1<=n) mn=min(mn,j-i+1);		} 	}	if (mn>=m+1) PRintf("-1/n");	else printf("%d/n",mn);*/	memset(f,0,sizeof(f));	int mn=m+1;	for (int i=1;i<=n;i++){		int a=0,b=0;		for (int j=1;j<=n;j++) {			if (s[i]==s1[j]) f[i][j]=f[i-1][j-1]+1;			a=max(f[i][j],a);		}		if (a!=i) mn=min(mn,a);	}	if (mn>=m+1) printf("-1/n");	else printf("%d/n",mn+1);} void solve2()//A的最短子串，不是B的子序列 {	memset(f,0,sizeof(f));	int mn=m+1;	for (int i=1;i<=n;i++){		int a=0,b=0;		for (int j=1;j<=m;j++) {			if (s[i]==s1[j]) f[i][j]=b+1;			a=max(a,f[i][j]);			b=max(b,f[i-1][j]); //f[i][j]表示A中的第i個(gè)字符匹配到B中第j個(gè)字符，A匹配時(shí)必須連續(xù) 		} 		if (a!=i) mn=min(mn,a);//匹配的長(zhǎng)度不是i說(shuō)明，在i+前一字符就是一個(gè)合法的子串 	}	if (mn>=m+1) printf("-1/n");	else printf("%d/n",mn+1);} void solve3()//A的最短的子序列，不是b的子串。 {	memset(len,127/3,sizeof(len));	len[1]=0; int mn=m+1; int t;	for (int i=1;i<=n;i++)	 for (int j=1;j<=cnt;j++)	  if (!(t=ch[j][s[i]-'a'+1])) mn=min(mn,len[j]);//如果到該點(diǎn)匹配不上了，說(shuō)明在當(dāng)前基礎(chǔ)上加入s[i]就能得到了一個(gè)合法的子序列 	  else len[t]=min(len[t],len[j]+1);//len表示的是用a的子序列去匹配后綴自動(dòng)機(jī)中的節(jié)點(diǎn)，到節(jié)點(diǎn)i能得到的最短長(zhǎng)度 	if (mn==m+1) printf("-1/n");	else printf("%d/n",mn+1);}void solve4(){	for (int i=m;i>=0;i--){//只要是在當(dāng)前位置之后出現(xiàn)的字符都可以用來(lái)構(gòu)造子序列，如果我們要選擇字符x，那么必然優(yōu)先選擇最靠近當(dāng)前位置的字符。 		for (int j=1;j<=26;j++)		 if (mp[j]) ch1[i][j]=mp[j];		mp[s1[i]-'a'+1]=i;	}	memset(len,127/3,sizeof(len));	len[0]=0;    int mn=m+1; int t;    for (int i=1;i<=n;i++)     for (int j=m;j>=0;j--)//這里與第三問(wèn)不同，必須倒序枚舉，因?yàn)檫@里相當(dāng)于是個(gè)背包，那么對(duì)于一個(gè)字符來(lái)說(shuō)，不能連續(xù)更新同一層中的位置，否則原串只有一個(gè)字符x，正序枚舉會(huì)出現(xiàn)xx的情況。       if (!(t=ch1[j][s[i]-'a'+1])) mn=min(mn,len[j]);      else len[t]=min(len[t],len[j]+1);     if (mn==m+1) printf("-1/n");    else printf("%d/n",mn+1);}int main()  {      freopen("sus4.in","r",stdin);      //freopen("sus.out","w",stdout);      scanf("%s",s+1);      scanf("%s",s1+1);      n=strlen(s+1); m=strlen(s1+1);       root=last=++cnt;      for (int i=1;i<=m;i++)       extend(i);      solve1();      solve2();    solve3();    solve4();}