题解 P3002【[USACO10DEC]Threatening Letter G】

· · 题解

看到题面，首先可以想到一个 DP：设 f(i) 为剪出第二封信的前 i 个字符所需要的最小次数，显然有 f(i)=1+\min_{i-val_i\le j<i} f(j)，其中 val_i 为以 i 结尾能够剪出的最大后缀长度。这个 DP 可以利用线段树优化成 O(n\log n)，所以关键在于如何求 val_i。

根据 “子串是前缀的后缀”，val_i 即为第二封信的前缀 i 与第一封信的任意前缀的 最大公共后缀。将两封信翻转，就变成了求第二封信的一个后缀与第一封信的任意后缀的 最大公共前缀。

将第一封信与第二封信拼在一起，中间用特殊字符连接，跑一遍后缀数组，求出 height(i)，根据 lcp(sa_i,sa_j)=\min_{i+1\le k\le j}height(k)，建立 ST 表就可以用 O(n\log n)-O(1) 的时间复杂度求出任意两个后缀的最大公共前缀。

根据上面的定理，若 sa_i 与 sa_j 距离越远，它们的最大公共前缀就越小。所以，在求 val_i 时，寻找 sa 数组上左右距离 rk_i 最近的两个点求最大公共前缀，然后取最大值即可。

每一步的时间复杂度均为 O(n\log n)，所以总时间复杂度为 O(n\log n)。

#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Rof(i,a,b) for(i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5,inf=1e9;

int m1,m2,n,i,j,m,p,t,seg[Maxn*4+5]; char s1[Maxn+5],s2[Maxn+5],s[Maxn+5],str[Maxn+5];
int sa[Maxn+5],rk[Maxn+5],ht[Maxn+5],cnt[Maxn+5],id[Maxn+5],px[Maxn+5],old[Maxn+5];
int f[Maxn+5],val[Maxn+5],pos[Maxn+5][2],lg[Maxn+5],st[Maxn+5][20],vis[Maxn+5];
inline int cmp(int x,int y) {return (old[x]==old[y] && old[x+t]==old[y+t]);}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

inline void Init()
{
    int res=0;
    scanf("%d%d",&m1,&m2); n=m1+m2+1,m=200;
    while(1)
    {
        scanf("%s",str+1); int siz=strlen(str+1);
        For(i,1,siz) s1[res+i]=str[i];
        res+=siz; if(res==m1) break;
    }
    res=0;
    while(1)
    {
        scanf("%s",str+1); int siz=strlen(str+1);
        For(i,1,siz) s2[res+i]=str[i];
        res+=siz; if(res==m2) break;
    }
    For(i,1,m1) s[i]=s1[m1-i+1];
    s[m1+1]='#';
    For(i,1,m2) s[m1+1+i]=s2[m2-i+1];
}
inline void SA()
{
    For(i,1,n) cnt[rk[i]=s[i]]++;
    For(i,1,m) cnt[i]+=cnt[i-1];
    Rof(i,n,1) sa[cnt[rk[i]]--]=i;
    for(t=1;t<=n;t<<=1,m=p)
    {
        for(p=0,i=n;i>n-t;--i) id[++p]=i;
        For(i,1,n) if(sa[i]>t) id[++p]=sa[i]-t;
        memset(cnt,0,sizeof(cnt));
        For(i,1,n) cnt[px[i]=rk[id[i]]]++;
        For(i,1,m) cnt[i]+=cnt[i-1];
        Rof(i,n,1) sa[cnt[px[i]]--]=id[i];
        memcpy(old,rk,sizeof(rk));
        for(p=0,i=1;i<=n;++i) rk[sa[i]]=(cmp(sa[i-1],sa[i])?p:++p);
    }
}
inline void Build()
{
    int res=0;
    For(i,1,n)
    {
        while(s[sa[rk[i]-1]+res]==s[i+res]) res++;
        ht[rk[i]]=res,res=max(0,res-1);
    }
}
inline void BuildST()
{
    For(i,2,n) lg[i]=lg[i>>1]+1;
    For(i,1,n) st[i][0]=ht[i];
    For(j,1,19) For(i,1,n)
    {
        st[i][j]=st[i][j-1];
        if(i+(1<<j-1)<=n) st[i][j]=min(st[i][j],st[i+(1<<j-1)][j-1]);
    }
}
inline int Count(int l,int r)
{
    int len=lg[r-l+1];
    return min(st[l][len],st[r-(1<<len)+1][len]);
}
inline void Tag()
{
    For(i,0,n+1) pos[i][0]=0,pos[i][1]=n+1;
    For(i,1,m1) vis[rk[i]]=1;
    For(i,1,n) pos[i][0]=(vis[i]?i:pos[i-1][0]);
    Rof(i,n,1) pos[i][1]=(vis[i]?i:pos[i+1][1]);
}
inline void GetVal(int x)
{
    int l=pos[rk[n-x+1]][0],r=pos[rk[n-x+1]][1];
    if(l) val[x]=max(val[x],Count(l+1,rk[n-x+1]));
    if(r!=n+1) val[x]=max(val[x],Count(rk[n-x+1]+1,r));
}
inline void push_up(int p) {seg[p]=min(seg[ls(p)],seg[rs(p)]);}
inline void Update(int l,int r,int p,int pos,int k)
{
    if(l==r) {seg[p]=k; return;}
    int mid=(l+r)>>1;
    if(pos<=mid) Update(l,mid,ls(p),pos,k);
    else Update(mid+1,r,rs(p),pos,k);
    push_up(p);
}
inline int Count(int nl,int nr,int l,int r,int p)
{
    if(l<=nl && nr<=r) return seg[p];
    int mid=(nl+nr)>>1,res=inf;
    if(l<=mid) res=min(res,Count(nl,mid,l,r,ls(p)));
    if(r>mid) res=min(res,Count(mid+1,nr,l,r,rs(p)));
    push_up(p); return res;
}
inline void GetAns()
{
    For(i,1,m2)
    {
        if(val[i]==i) f[i]=1;
        else f[i]=Count(1,n,i-val[i],i-1,1)+1;
        Update(1,n,1,i,f[i]);
    }
    printf("%d\n",f[m2]);
}

int main()
{
    Init(),SA(),Build(),BuildST(),Tag();
    For(i,1,m2) GetVal(i);
    GetAns();
    return 0;
}