题解 P6540 [COCI2013-2014#1] SLASTIČAR

· · 题解

首先，对于长序列号，建出它的 SAM。

先考虑不能够完全匹配的情况。
我们把短序列号在长序列号的 SAM 上匹配，前 i 个字符匹配到的 SAM 上的节点 x，根据 SAM 的性质，这前 i 个字符组成的前缀串应为 x 在 parent 树上的子树中任一（所有）节点对应串的后缀。也就是说，短串至少会在长串中 x 对应子树中所有点的 pos 集合的并中的每一个位置匹配一次。
另外，对于匹配不上的情况，出现了 n 次。

然后是能够完全匹配的情况。
大体同上，不过有一点，匹配上了以后会停止匹配。也就是说，设停止位置为 p，前 i 个字符的前缀只在前述集合中在 [1,p-(m-i)] 中的位置匹配上过。
另外，对于匹配不上的情况，出现了 p-m 次。

所以问题转化为询问一个点的子树中权值小于等于一个数的权值的个数。于是我们直接 dsu on tree 维护询问即可。 

#include<cstdio>
#include<vector>
#include<cstring>
const int N=2e5+10,M=10,Q=3e6+10;
int n,m,fa[N],to[N][M],len[N],pos[N],siz[N],son[N],cnt=1,las=1,a[Q],c[N];
bool vis[N];
long long ans[N];
std::vector<int>g[N];
std::vector<std::pair<int,int> >q[N];
inline void update(int x,int a){for(;x<=n;x+=x&-x)c[x]+=a;}
inline int query(int x){int a=0;for(;x;x-=x&-x)a+=c[x];return a;}
void insert(int c,int i)
{
    int p=las,q=++cnt;las=q;
    len[q]=len[p]+1;pos[q]=i;
    while(p&&!to[p][c])to[p][c]=q,p=fa[p];
    if(!p)fa[q]=1;
    else
    {
        int x=to[p][c];
        if(len[x]==len[p]+1)fa[q]=x;
        else
        {
            int y=++cnt;memcpy(to[y],to[x],sizeof(to[x]));
            fa[y]=fa[x];fa[x]=fa[q]=y;len[y]=len[p]+1;pos[y]=pos[x];
            while(p&&to[p][c]==x)to[p][c]=y,p=fa[p];
        }
    }
}
inline int min(int a,int b){return a<b?a:b;}
void dfs0(int u)
{
    siz[u]=1;
    for(int i=0,l=g[u].size();i<l;i++)
    {
        dfs0(g[u][i]);
        siz[u]+=siz[g[u][i]];
        pos[u]=min(pos[u],pos[g[u][i]]);
        if(siz[son[u]]<siz[g[u][i]])
        son[u]=g[u][i];
    }
}
int qwq,flg;
void dfs1(int u)
{
    if(pos[u]&&flg==1&&!vis[pos[u]])update(pos[u],1),vis[pos[u]]=true;
    if(pos[u]&&flg==-1&&vis[pos[u]])update(pos[u],-1),vis[pos[u]]=false;
    for(int i=0,l=g[u].size();i<l;i++)
    if(g[u][i]!=qwq)dfs1(g[u][i]);
}
void dfs(int u)
{
    for(int i=0,l=g[u].size();i<l;i++)
    if(g[u][i]!=son[u])dfs(g[u][i]);
    if(son[u])dfs(son[u]);
    qwq=son[u],flg=1;dfs1(u);
    for(int i=0,l=q[u].size();i<l;i++)
    ans[q[u][i].second]+=query(q[u][i].first);
    if(son[fa[u]]!=u)qwq=flg=-1,dfs1(u);
}
int main()
{
    int i,j,x,y;scanf("%d",&n);char ch;
    for(i=1;i<=n;i++)scanf("%1d",&x),insert(x,i);
    for(i=2;i<=cnt;i++)g[fa[i]].push_back(i);
    dfs0(1);scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        do ch=getchar(); while(ch<=32);a[0]=0;
        do a[++a[0]]=ch-'0',ch=getchar(); while(ch>='0'&&ch<='9');
        for(x=j=1;j<=a[0];j++)if(!to[x][a[j]])break;else x=to[x][a[j]];
        if(j<=a[0])y=n+a[0];else y=pos[x];ans[i]=y-a[0];
        for(x=j=1;j<=a[0];j++)if(!to[x][a[j]])break;else x=to[x][a[j]],q[x].push_back(std::make_pair(min(y-(a[0]-j),n),i));
    }
    dfs(1);
    for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
    return 0;
}