题解 P4094 【[HEOI2016/TJOI2016]字符串】

· · 题解

SAM

怎么题解都没有几篇SAM的，SAM会伤心的。

Part.1

首先观察询问，好像非常不可做，但是可以发现答案有可二分性，具体来说，可以二分最长公共前缀的长度，然后就是询问c到c+mid-1有没有在[a,b]出现过，然而SAM更擅长后缀，所以可以把串翻转过来求后缀匹配数。

如果对SAM敏感的就可以发现这其实就可以发现这是一个在SAM上线段树合并预处理然后倍增跳parent树查询的裸题了。

于是就完了（不是

Part.2

具体来说，我们知道一个endpos的父亲肯定是她的后缀，即如果当前点可以匹配，她的父亲肯定可以匹配。SAM上每个点我们都开一棵线段树，统计她可以匹配哪些前缀，首先前缀对应的节点肯定可以匹配自己，然后我们线段树合并答案。

每次假设我们钦定了右端点为r，我们就倍增的往上跳到最上面的r-maxlen+1\le l的节点，这个点包含了我们所有的需要的东西，直接查一遍即可。

做完了可以去做一下这个，跟这个比较像。

const int maxn=1e5+5;

struct SegmentTree
{
    int lc[maxn*40],rc[maxn*40],wife[maxn*40],cnt;
    void modify(int &u,int l,int r,int x)
    {
        if(!u) u=++cnt;
        ++wife[u];
        if(l==r) return;
        int mid=(l+r)>>1;
        if(x<=mid) modify(lc[u],l,mid,x);
        else modify(rc[u],mid+1,r,x);
    }
    int merge(int u,int v)
    {
        if(!u||!v) return u|v;
        int x=++cnt;
        wife[x]=wife[u]+wife[v];
        lc[x]=merge(lc[u],lc[v]);
        rc[x]=merge(rc[u],rc[v]);
        return x;
    }
    int query(int u,int l,int r,int x,int y)
    {
        if(!u) return 0;
        if(x<=l&&r<=y) return wife[u];
        int mid=(l+r)>>1,res=0;
        if(x<=mid) res+=query(lc[u],l,mid,x,y);
        if(y>mid) res+=query(rc[u],mid+1,r,x,y);
        return res;
    }
}wife;

int tr[maxn<<1][26],maxlen[maxn<<1],link[maxn<<1],cnt=1,las=1,tax[maxn<<1],a[maxn<<1];
int fa[maxn<<1][21],n,pos[maxn],rt[maxn<<1];
char s[maxn];

void insert(int c)
{
    int u=las,nu=las=++cnt;
    maxlen[nu]=maxlen[u]+1;
    for(;u&&!tr[u][c];u=link[u]) tr[u][c]=nu;
    if(!u) return link[nu]=1,void();
    int v=tr[u][c];
    if(maxlen[u]+1==maxlen[v]) return link[nu]=v,void();
    int nv=++cnt;
    maxlen[nv]=maxlen[u]+1;link[nv]=link[v];link[v]=link[nu]=nv;
    memcpy(tr[nv],tr[v],sizeof(tr[v]));
    for(;u&&tr[u][c]==v;u=link[u]) tr[u][c]=nv;
}

inline bool check(int lim,int u,int l,int r)
{
    for(int i=20;i>=0;--i) if(fa[u][i]&&maxlen[fa[u][i]]>=lim) u=fa[u][i];
    return wife.query(rt[u],1,n,l+lim-1,r);
}

int main()
{
    int q,x,y,c,d;
    scanf("%d%d%s",&n,&q,s+1);
    reverse(s+1,s+n+1);
    for(int i=1;i<=n;++i) insert(s[i]-'a'),pos[i]=las,wife.modify(rt[las],1,n,i);
    for(int i=1;i<=cnt;++i) ++tax[maxlen[i]],fa[i][0]=link[i];
    for(int i=1;i<=cnt;++i) tax[i]+=tax[i-1];
    for(int i=cnt;i;--i) a[tax[maxlen[i]]--]=i;
    for(int i=cnt;i>1;--i) rt[link[a[i]]]=wife.merge(rt[a[i]],rt[link[a[i]]]);
    for(int j=1;j<=20;++j)
        for(int i=1;i<=cnt;++i)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    while(q--)
    {
        scanf("%d%d%d%d",&x,&y,&c,&d);
        x=n-x+1;y=n-y+1;c=n-c+1;d=n-d+1;
        int l=0,r=min(x-y+1,c-d+1),mid,ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid,pos[c],y,x)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0,QAQ;
}