给出一个长为n的字符串s,然后每次询问给出一个长为m的字符串ss。
然后让ss从s的1位置开始匹配，一个位置匹配成功，cnt++。失配那么初始位置+1.知道成功匹配或者初始位置为n+1.
每次输出cnt。
n<=10W sigma(m)<=300W
后面这个范围是虚的，因为我要来了数据
这道题当初学SAM的时候看到了，觉得要是后缀树能像后缀trie一样从根节点开始一步一步沿着边上的字符向下走。那么这个世界就美好了。
具体怎么做呢？
注意到一但成功匹配，后面的初始位置就不计入ans了。
我们可以这么做。先跑一遍，看看第一次被哪个后缀匹配。不妨设为k，如果没有匹配成功，不妨设为n+1.
然后我们重复上面的跑一遍过程，假设当前在now位置，我们走ch字符到了nxt位置。
那么now所能到达的其他后缀且编号<k的与该串匹配，长度就会是根到now的长度。
（其实也可以每到一个节点就查询当前还在的前缀然后计算它对ans的贡献。）
我们可以对每个后缀节点编号。那么我们要做的就是查询一棵子树内权值<k的数的个数。主席树即可。
但是。。。我并不会把后缀树当成后缀trie来使，对后缀树也只知道把SAM反过来建parent树就是后缀树。
于是就一直坑着。。。
今天上午心血来潮继续战SAM。感觉不明白后缀树如何做串匹配。
后来询问了wyfcyx神犇才知道后缀树做串匹配是和SAM一样的。而后缀树支持在开头加入一个操作，所以串匹配必须从后往前匹配！
于是我傻逼的问能不能直接把字符串放到father到儿子的边上呢？感觉十分naive。。。
然后wyfcyx说好像可行的样子。
判断相同什么的可以二分+hash？
然后又在PoPoQQQ的帮助下，把字符串放到father上，改成把该字符串在原串中出现的某个区间放上去。
又因为从一个点出发到达不同的节点一定首字母不同，所以我们可以用首字母作为一阶判断。
然后再按字符串记录的位置一个一个匹配。
这样复杂度也是O（m）的。
所以我们就可以用像后缀trie一样玩后缀树啦！
然后上面的算法也可以实现了。
然后一下午+一晚上就浪在这份代码上了
代码大概长这样：
struct sam
{
int last,cnt,go[maxn][10],l[maxn];
int tot,sum[maxm],ls[maxm],rs[maxm],fa[maxn];
int pos[maxn][2],id[maxn],ed[maxn],color[maxn],rt[maxn];
int n,ti;
int head[maxn];
struct edge{int go,next;}e[maxn];
inline void add(int x,int y)
{
e[++tot]=(edge){y,head[x]};head[x]=tot;
}
struct rec{int l,r,to;}to[maxn][10];
char s[maxn],ss[maxn];
sam(){last=cnt=1;}
inline void add(int x)
{
int p=last,np=last=++cnt;l[np]=l[p]+1;
for(;p&&!go[p][x];p=fa[p])go[p][x]=np;
if(!p)fa[np]=1;
else
{
int q=go[p][x];
if(l[q]==l[p]+1)fa[np]=q;
else
{
int nq=++cnt;l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof(go[q]));
fa[nq]=fa[q];
fa[np]=fa[q]=nq;
for(;p&&go[p][x]==q;p=fa[p])go[p][x]=nq;
}
}
}
inline void dfs(int x)
{
pos[x][0]=++ti;id[ti]=x;
for4(i,x)
{
dfs(y);
ed[x]=ed[y]-(l[y]-l[x]);
to[x][s[ed[x]+1]-'0']=(rec){ed[x]+1,ed[y],y};
}
if(!head[x])ed[x]=n;
pos[x][1]=ti;
}
inline void update(int &y,int x,int l,int r,int z)
{
y=++tot;
sum[y]=sum[x]+1;
if(l==r)return;
ls[y]=ls[x];rs[y]=rs[x];
if(z<=mid)update(ls[y],ls[x],l,mid,z);
else update(rs[y],rs[x],mid+1,r,z);
}
inline void init()
{
n=read();
scanf("%s",s+1);
for3(i,n,1)color[cnt+1]=i,add(s[i]-'0');
for1(i,cnt)add(fa[i],i);
dfs(1);
tot=0;
for1(i,cnt)if(color[id[i]])update(rt[i],rt[i-1],1,n,color[id[i]]);else rt[i]=rt[i-1];
}
inline int getmi(int x,int y,int l,int r)
{
if(l==r)return l;
return sum[ls[y]]>sum[ls[x]]?getmi(ls[x],ls[y],l,mid):getmi(rs[x],rs[y],mid+1,r);
}
inline int query(int xx,int yy,int l,int r,int x,int y)
{
if(y<=0)return 0;
if(l==x&&r==y)return sum[yy]-sum[xx];
else if(y<=mid)return query(ls[xx],ls[yy],l,mid,x,y);
else if(x>mid)return query(rs[xx],rs[yy],mid+1,r,x,y);
else return query(ls[xx],ls[yy],l,mid,x,mid)+query(rs[xx],rs[yy],mid+1,r,mid+1,y);
}
int a[maxn],b[maxn],c[maxn];
inline void work()
{
scanf("%s",ss+1);int m=strlen(ss+1);
int now=1,ret,t=1,k=0;
while(t<=m)
{
a[++k]=now;b[k]=t;
int x=ss[t]-'0';rec y=to[now][x];
if(!y.l&&!y.r){break;}
now=y.to;
int j=y.l;
while(t<=m&&j<=y.r&&ss[t]==s[j])t++,j++;
if(t>m)break;
if(j<=y.r){a[++k]=y.to;b[k]=t;break;}
}
ll ans=0;
if(t<=m)ret=n+1;
else ans=m,ret=getmi(rt[pos[now][0]-1],rt[pos[now][1]],1,n);
for1(i,k)c[i]=query(rt[pos[a[i]][0]-1],rt[pos[a[i]][1]],1,n,1,ret-1);
c[k+1]=0;
for1(i,k)ans+=(c[i]-c[i+1])*b[i];
printf("%lld\n",ans);
}
}SAM;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
SAM.init();
int T=read();
while(T--)SAM.work();
return 0;
}
如果哪里写得丑或者可以优化希望神犇们能提出来。
当然我知道这道题肯定有很简单的方法，但是做此题的收获主要是后缀树的新姿势get√
评论 (0)
