5
14
2015
0

BZOJ3413: 匹配

给出一个长为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√

Category: 涨姿势 | Tags: | Read Count: 690

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com