BZOJ4032:[HEOI2015]最短不公共子串(SAM)

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

Solution

强行四合一？

（一）枚举$A$串的左端点，然后从左端点开始往后在$B$串的$SAM$上面跑，一旦失配就更新答案然后$break$

（二）预处理数组$next[i][j]$表示从$i$后面的第一次出现字母$j$的位置。预处理出$nextA$和$nextB$，然后枚举$A$左端点往后贪心，如果失配就更新答案然后$break$

（三）设$len[i]$表示在$B$串的$SAM$的$i$点的时候最短的长度。然后用$A$串在$B$的$SAM$上面跑。如果失配就更新答案，否则就更新$len$。

（四）设$len[i]$表示在$B$串的$i$位置的时候最短的长度。然后用$A$串的每一个字母，借$next$数组倒序去更新$len$。如果失配就更新答案，否则就更新$len$。至于为什么要倒序，其实是和背包差不多的原理，并不难想。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (4009)

 using namespace std;

 char s[N],t[N];

 int slen,tlen,nextA[N][],nextB[N][],last[],len[N];

 struct SAM

 {

     int son[N][],fa[N],step[N],wt[N],od[N];

     int p,q,np,nq,last,cnt;

     SAM(){last=cnt=;}

     void Insert(int x)

     {

         p=last; np=last=++cnt; step[np]=step[p]+;

         while (p && !son[p][x]) son[p][x]=np, p=fa[p];

         if (!p) fa[np]=;

         else

         {

             q=son[p][x];

             if (step[q]==step[p+]) fa[np]=q;

             else

             {

                 nq=++cnt; step[nq]=step[p]+;

                 memcpy(son[nq],son[q],sizeof(son[q]));

                 fa[nq]=fa[q]; fa[np]=fa[q]=nq;

                 while (son[p][x]==q) son[p][x]=nq, p=fa[p];

             }

         }

     }

 }SAM;

 void CalcNext()

 {

     memset(last,-,sizeof(last));

     for (int i=slen; i>=; --i)

     {

         for (int j=; j<; ++j) nextA[i][j]=last[j];

         last[s[i]-'a']=i;

     }

     memset(last,-,sizeof(last));

     for (int i=tlen; i>=; --i)

     {

         for (int j=; j<; ++j) nextB[i][j]=last[j];

         last[t[i]-'a']=i;

     }

 }

 void Sub1()

 {

     int ans=2e9;

     for (int i=; i<=slen; ++i)

     {

         int now=;

         for (int j=i; j<=slen; ++j)

         {

             if (!SAM.son[now][s[j]-'a']) {ans=min(ans,j-i+); break;}

             now=SAM.son[now][s[j]-'a'];

         }

     }

     printf("%d\n",ans==2e9?-:ans);

 }

 void Sub2()

 {

     int ans=2e9;

     for (int i=; i<=slen; ++i)

     {

         int now=;

         for (int j=i; j<=slen; ++j)

         {

             if (nextB[now][s[j]-'a']==-) {ans=min(ans,j-i+); break;}

             now=nextB[now][s[j]-'a'];

         }

     }

     printf("%d\n",ans==2e9?-:ans);

 }

 void Sub3()

 {

     int ans=2e9;

     memset(len,0x7f,sizeof(len));

     len[]=;

     for (int i=; i<=slen; ++i)

         for (int j=; j<=SAM.cnt; ++j)

         {

             int nxt=SAM.son[j][s[i]-'a'];

             if (!nxt) ans=min(ans,len[j]);

             else len[nxt]=min(len[nxt],len[j]+);

         }

     printf("%d\n",ans==2e9?-:ans);

 }

 void Sub4()

 {

     int ans=2e9;

     memset(len,0x7f,sizeof(len));

     len[]=;

     for (int i=; i<=slen; ++i)

         for (int j=tlen; j>=; --j)

         {

             int nxt=nextB[j][s[i]-'a'];

             if (nxt==-) ans=min(ans,len[j]+);

             else len[nxt]=min(len[nxt],len[j]+);

         }

     printf("%d\n",ans==2e9?-:ans);

 }

 int main()

 {

     scanf("%s%s",s+,t+);

     slen=strlen(s+), tlen=strlen(t+);

     for (int i=; i<=tlen; ++i)

         SAM.Insert(t[i]-'a');

     CalcNext();

     Sub1(); Sub2(); Sub3(); Sub4();

 }

巴特西