bzoj Luogu

给两个小写字母串 $ 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\n",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\n",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\n",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\n",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();}