bzoj4032/luoguP4112 [HEOI2015]最短不公共子串(后缀自动机+序列自动机上dp)
题解时间
给两个小写字母串 $ A $ ， $ B $ ，请你计算：
(1) $ A $ 的一个最短的子串，它不是 $ B $ 的子串
(2) $ A $ 的一个最短的子串，它不是 $ B $ 的子序列
(3) $ A $ 的一个最短的子序列，它不是 $ B $ 的子串
(4) $ A $ 的一个最短的子序列，它不是 $ B $ 的子序列
水题四合一，一题更比四题sao
首先由于都是要从 $ A $ 中找，所以按照套路是把 $ A $ 在 $ B $ 上匹配
所以先构建出 $ B $ 的SAM和序列自动机。
序列自动机：就是一个 $ next[i][ch] $ 数组表示第 $ i $ 位往后第一个出现字符 $ ch $ 的位置，纯粹用来匹配的。
(1) 直接以 $ A $ 每一位为起点在 $ B $ 的SAM上暴力匹配，只要失配就更新答案然后跳出。
(2) 换成在序列自动机上。
(3) $ dp[i][j] $ 表示 $ A $ 的前 $ i $ 个字符形成的子序列在 $ B $ 的SAM上匹配到了 $ j $ 位置，此时形成的最短子序列长度，这是个挺经典的dp了。
(4) 换成在序列自动机上。
#include<bits/stdc++.h>
using namespace std;
namespace RKK
{
const int N=2011,inf=0x3f3f3f3f;
int n1;char s1[N];
int n2;char s2[N];
struct remilia{int tranc[26],len,pre;};
struct sakuya
{
remilia s[N<<1];
int fin,size;
sakuya(){fin=size=1;}
void ins(int ch)
{
int npx,npy,lpx,lpy;
npx=++size;
s[npx].len=s[fin].len+1;
for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;
if(!lpx) s[npx].pre=1;
else
{
lpy=s[lpx].tranc[ch];
if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;
else
{
npy=++size;
s[npy]=s[lpy];
s[npy].len=s[lpx].len+1;
s[lpy].pre=s[npx].pre=npy;
while(s[lpx].tranc[ch]==lpy)
{
s[lpx].tranc[ch]=npy;
lpx=s[lpx].pre;
}
}
}
fin=npx;
}
void insert(char *str,int sl)
{
for(int i=1;i<=sl;i++)
ins(str[i]-'a');
}
}sam;
struct flandre
{
int ne[N][26],tmp[26];
void insert(char *s,int sl)
{
for(int i=sl;i>=0;i--)
memcpy(ne[i],tmp,104),tmp[s[i]-'a']=i;
}
}sem;
void solve1()
{
int ans=inf;
for(int sp=1;sp<=n1;sp++)
{
int px=1;
for(int i=sp;i<=n1;i++)
{
if(!sam.s[px].tranc[s1[i]-'a']){ans=min(ans,i-sp+1);break;}
px=sam.s[px].tranc[s1[i]-'a'];
}
}
printf("%d
",ans==inf?-1:ans);
}
void solve2()
{
int ans=inf;
for(int sp=1;sp<=n1;sp++)
{
int px=0;
for(int i=sp;i<=n1;i++)
{
if(!sem.ne[px][s1[i]-'a']){ans=min(ans,i-sp+1);break;}
px=sem.ne[px][s1[i]-'a'];
}
}
printf("%d
",ans==inf?-1:ans);
}
int dp[N<<1];
void solve3()
{
int ans=inf;
memset(dp,0x3f,sizeof(dp));
dp[1]=0;
for(int i=1;i<=n1;i++)
{
for(int x=sam.size;x;x--)
{
if(sam.s[x].tranc[s1[i]-'a']) dp[sam.s[x].tranc[s1[i]-'a']]=min(dp[sam.s[x].tranc[s1[i]-'a']],dp[x]+1);
else ans=min(ans,dp[x]+1);
}
}
printf("%d
",ans==inf?-1:ans);
}
void solve4()
{
int ans=inf;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n1;i++)
{
for(int x=n2;x>=0;x--)
{
if(!sem.ne[x][s1[i]-'a']) ans=min(ans,dp[x]+1);
else dp[sem.ne[x][s1[i]-'a']]=min(dp[sem.ne[x][s1[i]-'a']],dp[x]+1);
}
}
printf("%d
",ans==inf?-1:ans);
}
int Iris()
{
scanf("%s%s",s1+1,s2+1),n1=strlen(s1+1),n2=strlen(s2+1);
sam.insert(s2,n2),sem.insert(s2,n2);
solve1(),solve2(),solve3(),solve4();
return 0;
}
}
int main(){return RKK::Iris();}