本文共 3808 字，大约阅读时间需要 12 分钟。
题目大意： 给出一个串 S S S，然后给出 m m m 个串，每个串记作 T i T_i Ti，给出 k k k 个询问，每次询问 S S S 的一个子串在 T l T_l Tl ~ T r T_r Tr 中的哪个字符串中出现次数最多，并输出出现次数。
题解
显然要先建出广义SAM，然后每次询问 S S S 的一个子串时，提前建出后缀链接树，在上面跑倍增就能找到这个子串对应的状态，然后利用这个状态的endpos集就可以求解，看看在哪个字符串中出现次数最多即可。
具体来说就是在每个状态上建一棵线段树，记录该状态在每个字符串中的出现次数以及维护一下最大值，然后利用线段树合并搞一搞。
代码如下：
#include #include #include #include using namespace std;#define maxn 1000010char s[maxn],ss[maxn];int n,m,pos[maxn],k;//一开始把他们的类型也弄成char了然后瞎调半天没搞明白……struct par{ int ma,from;};struct node{ int l,r,ma,from; node *zuo,*you; node(int x,int y):l(x),r(y),ma(0),from(0),zuo(NULL),you(NULL){ } #define mid (l+r>>1) void build(int x) { ma=1;if(l==r){ from=l;return;} if(x<=mid)zuo=new node(l,mid),zuo->build(x),from=zuo->from; else you=new node(mid+1,r),you->build(x),from=you->from; } void update() { if(zuo==NULL)ma=you->ma,from=you->from; else if(you==NULL)ma=zuo->ma,from=zuo->from; else if(zuo->from==you->from)from=zuo->from,ma=zuo->ma+you->ma; else if(zuo->ma==you->ma)from=min(zuo->from,you->from),ma=zuo->ma; else if(zuo->ma>you->ma)ma=zuo->ma,from=zuo->from; else ma=you->ma,from=you->from; } par ask(int x,int y) { if(l==x&&r==y)return (par){ ma,from}; if(y<=mid){ if(zuo!=NULL)return zuo->ask(x,y);} else if(x>=mid+1){ if(you!=NULL)return you->ask(x,y);} else { par re,p;re.ma=re.from=0; if(zuo!=NULL){ p=zuo->ask(x,mid);if(p.ma>re.ma)re=p;} if(you!=NULL){ p=you->ask(mid+1,y);if(p.ma>re.ma)re=p;} return re; } return (par){ 0,0}; }};struct state{ int link,len,next[26]; node *root; state():root(NULL){ }}st[maxn<<1];int id=0,last=0,now,p,q,size[maxn<<1];void extend(int x,int belong){ now=++id;st[now].len=st[last].len+1; if(belong>1)st[now].root=new node(1,m),st[now].root->build(belong-1); for(p=last;p!=-1&&!st[p].next[x];p=st[p].link)st[p].next[x]=now; if(p!=-1) { q=st[p].next[x]; if(st[p].len+1==st[q].len)st[now].link=q; else { int clone=++id; st[clone]=st[q];st[clone].len=st[p].len+1;st[clone].root=NULL; for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone; st[q].link=st[now].link=clone; } } last=now;}struct edge{ int y,next;};edge e[maxn<<1];int first[maxn<<1],len=0;void buildroad(int x,int y){ e[++len]=(edge){ y,first[x]};first[x]=len;}int f[maxn<<1][20],g[maxn<<1];int kk(int x){ return st[x].len-st[st[x].link].len;}void dfs_prepare(int x){ for(int i=first[x];i;i=e[i].next) f[e[i].y][0]=x,g[e[i].y]=kk(e[i].y)+g[x],dfs_prepare(e[i].y);}node *merge(node *x,node *y){ if(x==NULL)return y; if(y==NULL)return x; node *now=new node(x->l,x->r); now->zuo=merge(x->zuo,y->zuo); now->you=merge(x->you,y->you); if(now->l==now->r)now->from=now->l,now->ma=x->ma+y->ma; else now->update(); return now;}struct que{ int x,y,pos;};vector ask[maxn<<1];par ans[maxn];int left[maxn];void dfs(int x){ if(st[x].root==NULL)st[x].root=new node(1,m); for(int i=first[x];i;i=e[i].next) { int y=e[i].y;dfs(y); if(st[y].root->ma)st[x].root=merge(st[x].root,st[y].root); } for(int i=0;i ask(ask[x][i].x,ask[x][i].y);}int main(){ scanf("%s",s+1);n=strlen(s+1); st[0].link=-1; for(int i=1;i<=n;i++)pos[i]=id+1,extend(s[i]-'a',1); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",ss+1);n=strlen(ss+1);last=0; for(int j=1;j<=n;j++)extend(ss[j]-'a',i+1); } for(int i=1;i<=id;i++)buildroad(st[i].link,i); dfs_prepare(0); for(int j=1;j<20;j++) for(int i=1;i<=id;i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d",&k); for(int i=1,x,y,xx,yy;i<=k;i++) { scanf("%d %d %d %d",&x,&y,&xx,&yy); int now=pos[yy]; for(int j=19;j>=0;j--) if(f[now][j]&&g[f[now][j]]>=yy-xx+1)now=f[now][j]; ask[now].push_back((que){ x,y,i}); left[i]=x; } dfs(0); for(int i=1;i<=k;i++)printf("%d %d\n",!ans[i].from?left[i]:ans[i].from,ans[i].ma);}
转载地址：http://cnnib.baihongyu.com/