HRY and repeaters

C++14(g++5.4) 解法, 执行用时: 1652ms, 内存消耗: 181848K, 提交时间: 2019-05-05 10:06:16

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300005;
typedef long long ll;
int nxt[maxn<<1][30],fail[maxn<<1],len[maxn<<1],b[maxn<<1],c[maxn<<1];
int Root,tot,last,t,ans,l,r,n;
long long tree[maxn*50];
int ls[maxn*50],rs[maxn*50];
int root[maxn<<1],Q;
char s[maxn];
void update(int&rt,int pos,int l,int r){
	int mid=l+r>>1;
	if (pos<l||pos>r) return;
	if (!rt)
		rt=++t;
	if (pos==l&&pos==r){
		tree[rt]++;
		return;
	}
	update(ls[rt],pos,l,mid);
	update(rs[rt],pos,mid+1,r);
	tree[rt]=tree[ls[rt]]+tree[rs[rt]];
}
int query(int rt,int L,int R,int l,int r){
	if (L>r||l>R||!rt) return 0;
	if (L<=l&&R>=r) return tree[rt];
	int mid=l+r>>1;
	return query(ls[rt],L,R,l,mid)+query(rs[rt],L,R,mid+1,r);
}
void extend(int c,int t){
	if (nxt[last][c]&&len[nxt[last][c]]==len[last]+1){
		last=nxt[last][c];
		update(root[last],t,1,n);
		return;
	}
	int p=last,np=++tot;
	last=np;
	len[np]=len[p]+1;
	for (;p&&!nxt[p][c];p=fail[p]) nxt[p][c]=np;
	if (!p)
		fail[np]=Root;
	else{
		int q=nxt[p][c];
		if (len[q]==len[p]+1)
			fail[np]=q;
		else{
			int nq=++tot;
			memcpy(nxt[nq],nxt[q],sizeof(nxt[nq]));
			fail[nq]=fail[q];
			fail[q]=fail[np]=nq;
			len[nq]=len[p]+1;
			for(;p&&nxt[p][c]==q;p=fail[p]) nxt[p][c]=nq;
		}
	}
	update(root[np],t,1,n);
}
int merge(int p,int q){
	if (!p||!q)
		return p+q;
	int z=++t;
	tree[z]=tree[p]+tree[q];
	ls[z]=merge(ls[p],ls[q]);
	rs[z]=merge(rs[p],rs[q]);
	return z;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	tot=Root=1;
	for (int i=1;i<=n;i++){
		cin >> s;
		int len=strlen(s);
		last=1;
		for (int j=0;j<len;j++)
			extend(s[j]-'a',i);
	}
	for (int i=1;i<=tot;i++) c[len[i]]++;
	for (int i=1;i<=tot;i++) c[i]+=c[i-1];
	for (int i=1;i<=tot;i++) b[c[len[i]]--]=i;
	for (int i=tot;i>=2;i--){
		int u=b[i];
		root[fail[u]]=merge(root[fail[u]],root[u]);
	}
	cin >> Q;
	for (int i=1;i<=Q;i++){
		cin >> l >> r;
		l^=ans;r^=ans;
		cin >> s;
		int len=strlen(s),cur=Root;
		bool flag=true;
		for (int j=0;j<len;j++){
			if (nxt[cur][s[j]-'a'])
				cur=nxt[cur][s[j]-'a'];
			else{
				flag=false;
				break;
			}
		}
		if (flag){
			cout << (ans=query(root[cur],l,r,1,n)) << '\n';
		}else
			cout << (ans=0) << '\n';
	}
} /*
1
gugugu
1
1 1 gu*/

C++11(clang++ 3.9) 解法, 执行用时: 617ms, 内存消耗: 166348K, 提交时间: 2019-04-29 16:13:56

#include<bits/stdc++.h>
#define lson ls[x],l,mid
#define rson rs[x],mid+1,r 
using namespace std;const int N=6e5+7,M=N*40;
int a[N][26],n,m,i,j,c[N],ls[M],rs[M],l[N],sum[M],root[N],fa[N],t[N],len,last=1,Sz,np,nq,p,q,sz=1,L,R,ans;string tmp,s[N];
int merge(int x,int y){
	if(!x||!y)return x+y;
	int z=++Sz;sum[z]=sum[x]+sum[y];
	ls[z]=merge(ls[x],ls[y]);rs[z]=merge(rs[x],rs[y]);
	return z;
}
void update(int&x,int l,int r,int pos){
	if(!x)x=++Sz;sum[x]++;if(l==r)return;int mid=l+r>>1;
	if(pos<=mid)update(lson,pos);else update(rson,pos);
}
int query(int x,int l,int r,int a,int b){
	if(a<=l&&r<=b||x==0)return sum[x];int mid=l+r>>1,res=0;
	if(a<=mid)res+=query(lson,a,b);if(b>mid)res+=query(rson,a,b);return res;
}
void add(int c){
	p=last;np=last=++sz;l[np]=l[p]+1;
	while(p&&!a[p][c])a[p][c]=np,p=fa[p];
	if(!p)fa[np]=1;
	else{
		q=a[p][c];
		if(l[p]+1==l[q])fa[np]=q;
		else{
			nq=++sz;l[nq]=l[p]+1;
			memcpy(a[nq],a[q],sizeof(a[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			while(a[p][c]==q)a[p][c]=nq,p=fa[p];
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	for(cin>>n,i=1;i<=n;++i)for(cin>>s[i],len=max(len,(int)s[i].size()),last=1,j=0;j<s[i].size();++j)add(s[i][j]-'a');
	for(i=1;i<=n;++i){
		for(j=0,p=1;j<s[i].size();++j)p=a[p][s[i][j]-'a'],update(root[p],1,n,i);
	}
	for(i=1;i<=sz;++i)c[l[i]]++;
	for(i=1;i<=len;++i)c[i]+=c[i-1];
	for(i=1;i<=sz;++i)t[c[l[i]]--]=i;
	for(i=sz;i>=2;--i)root[fa[t[i]]]=merge(root[fa[t[i]]],root[t[i]]);
	for(cin>>m;m--;){
		cin>>L>>R>>tmp;L^=ans;R^=ans;
		for(p=1,i=0;i<tmp.size();++i)p=a[p][tmp[i]-'a'];
		printf("%d\n",(ans=query(root[p],1,n,L,R)));
	}
}

详情