【BZOJ4032】[HEOI2015]最短不公共子串

2016.03.22 16:48 Tue | 49次阅读 | 旧日oi | 固定链接 | 源码

题解

trie树+dp

把b串建立后缀trie。
第一问枚举a的起点在trie上跑就行
第二问直接枚举a的子串就行,需要记录一个数组nxt,nxt[i][j]表示位置i后下一个字符j在哪。
第三问直接在trie上dfs一下就行。
第四问也是dp搞搞就好了f[i][j]表示a串到i,b串到j的最小长度,枚举下一个字符是什么转移即可。
4道题……每道都不难……

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 2005
char s[N];
int a[N],b[N],n,m;
int pos[26],nxt[N][26],nxt1[N][26];
int f[N][N];
int ans1=0x3f3f3f3f,ans2=0x3f3f3f3f,ans3=0x3f3f3f3f,ans4=0x3f3f3f3f;
struct Trie
{
    int son[2001005][26],tot;
    void insert(int x)
    {
        if(!tot) tot=1;
        for(int p=1,i=x;i<=m;i++)
        {
            if(!son[p][b[i]]) son[p][b[i]]=++tot;
            p=son[p][b[i]];
        }
    }
    void solve1()
    {
        for(int i=1;i<=n;i++)
        {
            int p=1;
            for(int j=i;j<=n;j++) 
            {
                if(!son[p][a[j]])
                {
                    ans1=min(ans1,j-i+1);
                    break;
                }
                p=son[p][a[j]];
            }
        }
        if(ans1==0x3f3f3f3f) ans1=-1;
        printf("%d\n",ans1);
    }
    void dfs(int u,int f,int d)
    {
        for(int i=0;i<26;i++)
        {
            if(nxt1[f][i]<=n&&!son[u][i])
            {
                ans3=min(ans3,d+1);
                return;
            }
            else if(nxt1[f][i]<=n) dfs(son[u][i],nxt1[f][i],d+1);
        }
    }
    void solve3()
    {
        dfs(1,0,0);
        if(ans3==0x3f3f3f3f) ans3=-1;
        printf("%d\n",ans3);
    }
}trie;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'a';
    scanf("%s",s+1);m=strlen(s+1);
    for(int i=1;i<=m;i++) b[i]=s[i]-'a';
    for(int i=1;i<=m;i++) trie.insert(i);
    trie.solve1();
    for(int i=0;i<26;i++) pos[i]=m+1;
    for(int i=m;i>=0;i--)
    {
        for(int j=0;j<26;j++) nxt[i][j]=pos[j];
        pos[b[i]]=i;
    }
    for(int i=0;i<26;i++) pos[i]=n+1;
    for(int i=n;i>=0;i--)
    {
        for(int j=0;j<26;j++) nxt1[i][j]=pos[j];
        pos[a[i]]=i;
    }
    int ans2=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        int x=0,tmp=0,k=i;
        while(k<=n)
        {
            x=nxt[x][a[k]];
            if(x>m) break;
            tmp++;k++;
        }
        if(k<=n) ans2=min(ans2,tmp+1);
    }
    if(ans2==0x3f3f3f3f) ans2=-1;
    printf("%d\n",ans2);
    trie.solve3();
    memset(f,0x3f,sizeof(f));f[0][0]=0;
    int ans4=0x3f3f3f3f;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<26;k++) 
            {
                if(nxt[j][k]<=m&&nxt1[i][k]<=n)
                    f[nxt1[i][k]][nxt[j][k]]=min(f[nxt1[i][k]][nxt[j][k]],f[i][j]+1);
                else if(nxt[j][k]>m&&nxt1[i][k]<=n) 
                    ans4=min(ans4,f[i][j]+1);
            }
        }
    }
    if(ans4==0x3f3f3f3f) ans4=-1;
    printf("%d\n",ans4);
}