【HEOI2015】最短不公共子串

后缀自动机+序列自动机

分别建出A,B两个串的后缀自动机和序列自动机，然后因为后缀自动机和序列自动机都是DAG，所以在上面dp一下就可以啦

dp[ i ][ j ]表示在第一个状态的自动机上匹配到 i 号节点，在第二个状态的自动机上匹配到 j 号节点时还需要添加dp[ i ][ j ]个字符才能使两串失配(满足条件) ，这个记忆化搜索一下就好了

复杂度:O（N+N*N）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int inf=1e9+10;
const int maxn=1e4+10;
struct suda
{
 struct da{int ch[30],fa,len;}po[maxn];
 int las,tot;
 void init()
 {
  memset(po,0,sizeof po); 
  las=tot=1;
 }
 void insert(int x)
 {
  int p=las,np=las=++tot; po[np].len=po[p].len+1;
  for (;p&&(!po[p].ch[x]);p=po[p].fa) po[p].ch[x]=np;
  if (!p) po[np].fa=1;
  else 
  {
   int q=po[p].ch[x];
   if (po[q].len==po[p].len+1) po[np].fa=q;
   else
   {
    int nq=++tot; po[nq]=po[q];
    po[nq].len=po[p].len+1;
    po[q].fa=po[np].fa=nq;
    for (;p&&(po[p].ch[x]==q);p=po[p].fa) po[p].ch[x]=nq;
   }
  }
 }
}SAM[3];
struct xuda
{
 struct da{int ch[30];}po[maxn];
 int lc[30];
 void init()
 {
  memset(po,0,sizeof po);
  memset(lc,0,sizeof lc);
 }
 void build(char *s,int n)
 {
  for (int i=n;i>=0;i--)
  {
   for (int j=0;j<26;j++) po[i].ch[j]=lc[j];
   lc[s[i]-'a']=i;
  }
 }
}XUM[3];
int lena,lenb,ans;
char a[maxn],b[maxn];
int dp[4010][4010];
int solve1(int x,int y)
{
 if (dp[x][y]) return dp[x][y];
 int now=inf;
 for (int i=0;i<26;i++)
 if (SAM[1].po[x].ch[i] && SAM[2].po[y].ch[i])
 {
   now=min(now,solve1(SAM[1].po[x].ch[i],SAM[2].po[y].ch[i])+1);
 }
 else if (SAM[1].po[x].ch[i] && !SAM[2].po[y].ch[i]) now=1;
 dp[x][y]=now;
return dp[x][y];
}
int solve2(int x,int y)
{
 if (dp[x][y]) return dp[x][y];
 int now=inf;
 for (int i=0;i<26;i++)
 if (SAM[1].po[x].ch[i] && XUM[2].po[y].ch[i])
 {
   now=min(now,solve2(SAM[1].po[x].ch[i],XUM[2].po[y].ch[i])+1);
 }
 else if (SAM[1].po[x].ch[i] && !XUM[2].po[y].ch[i]) now=1;
 dp[x][y]=now;
return dp[x][y];
}
int solve3(int x,int y)
{
 if (dp[x][y]) return dp[x][y];
 int now=inf;
 for (int i=0;i<26;i++)
 if (XUM[1].po[x].ch[i] && SAM[2].po[y].ch[i])
 {
   now=min(now,solve3(XUM[1].po[x].ch[i],SAM[2].po[y].ch[i])+1);
 }
 else if (XUM[1].po[x].ch[i] && !SAM[2].po[y].ch[i]) now=1;
 dp[x][y]=now;
return dp[x][y];
}
int solve4(int x,int y)
{
 if (dp[x][y]) return dp[x][y];
 int now=inf;
 for (int i=0;i<26;i++)
 if (XUM[1].po[x].ch[i] && XUM[2].po[y].ch[i])
 {
   now=min(now,solve4(XUM[1].po[x].ch[i],XUM[2].po[y].ch[i])+1);
 }
 else if (XUM[1].po[x].ch[i] && !XUM[2].po[y].ch[i]) now=1;
 dp[x][y]=now;
return dp[x][y];
}
int main()
{
 scanf("%s%s",a+1,b+1); lena=strlen(a+1); lenb=strlen(b+1);
 for (int i=1;i<=2;i++) SAM[i].init(),XUM[i].init();
 for (int i=1;i<=lena;i++) SAM[1].insert(a[i]-'a');
 XUM[1].build(a,lena);
 for (int i=1;i<=lenb;i++) SAM[2].insert(b[i]-'a');
 XUM[2].build(b,lenb);
 memset(dp,0,sizeof dp); ans=solve1(1,1); printf("%d\n",ans==inf?-1:ans);
 memset(dp,0,sizeof dp); ans=solve2(1,0); printf("%d\n",ans==inf?-1:ans);
 memset(dp,0,sizeof dp); ans=solve3(0,1); printf("%d\n",ans==inf?-1:ans);
 memset(dp,0,sizeof dp); ans=solve4(0,0); printf("%d\n",ans==inf?-1:ans);
return 0;
}