这道题市面上就两种法:一种是SA+二分+主席树,一种是SAM+二分+主席树(有不少人打线段树合并???)(除此之外还有一种利用炒鸡水的数据的暴力SA,贼快.....)(当时学SA的时候没做这道题,现在早忘了SA了)

　　分析题意:就是对于一个字符串,每次询问一个子串在另一个子串里能匹配上的最大前缀(非严格前缀)长度.

　　我们知道,处理前缀的工具并不是十分充足,后缀倒是有一大帮,所以说把字符串倒过来,而把字符串倒过来是SAM处理问题时的常用技巧.现在,我们直接找答案,仍然很难找到一种时间复杂度合法的做法,那么我们发现这个东西,是具有可二分的性质的,所以我们二分.这时,我们的问题转化为了"给出某个子串的right和len,快速求出其在某一区间内有无相同子串",然后利用SAM的节点的性质,我们又可以把问题转化为"给出某个子串的right和len,询问其所在节点的right集合是否存在元素在某一区间",到此,我们的问题已经很清晰了.

　　对于找到这个子串所在的节点,我们可以找到其right所对应的前缀所在的节点(这个我们在构造的时候就可以处理出来),然后在parent树上倍增找到包含有长度为len的子串的节点,接下来就是看在其right集合中是否存在元素在某个区间内,这个时候我们就可以搞出parent树的dfs序,并对dfs序建立主席树,主席树的线段树区间维护的是right集合.

　　好了我们得到了一种O(nlog^2n)的优秀做法！！！

#include 
     
      #include 
      
       #include 
       
        char xB[(1<<15)+10],*xS=xB,*xT=xB;#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)inline void read(int &x){  register char ch=gtc;bool symbol=false;  for(x=0;ch<'0'||ch>'9';ch=gtc)if(ch=='-')symbol=true;  for(;ch>='0'&&ch<='9';x=(x<<1)+(x<<3)+ch-'0',ch=gtc);  if(symbol)x=-x;}const int N=100010;const int A=26;const int B=20;char s[N],tmp[N];int pos[N];int trans[N<<1][A],max[N<<1],link[N<<1];int last,rt,sz;#define newnode(a) (max[++sz]=(a),sz)int id[N<<1],dfn[N<<1],L[N<<1],R[N<<1];int n,m;struct V{  int to,next;}c[N<<1];int head[N<<1],t;inline void add(int x,int y){  c[++t].to=y,c[t].next=head[x],head[x]=t;}int f[N<<1][B];int Ti;struct Segment_Tree{  Segment_Tree *ch[2];  int size;  inline void* operator new (size_t);}*root[N<<1],*C,*mempool,*null;#define mid ((l+r)>>1)inline void* Segment_Tree:: operator new(size_t){  if(C==mempool){    C=new Segment_Tree[(1<<16)+10];    mempool=C+(1<<16)+10;  }  return C++;}inline void Init(){  null=new Segment_Tree;  null->ch[0]=null->ch[1]=null;  null->size=0;  root[0]=null;  last=rt=newnode(0);}int w,q,nw,nq;inline void insert(int x){  w=last,nw=newnode(max[w]+1);  while(w&&trans[w][x]==0)trans[w][x]=nw,w=link[w];  if(!w)link[nw]=rt;  else if(max[w]+1==max[trans[w][x]])    link[nw]=trans[w][x];  else{    q=trans[w][x],nq=newnode(max[w]+1);    memcpy(trans[nq],trans[q],sizeof(trans[nq]));    while(w&&trans[w][x]==q)trans[w][x]=nq,w=link[w];    link[nq]=link[q],link[q]=link[nw]=nq;  }  last=nw,id[nw]=max[nw],pos[max[nw]]=nw;}inline void insert(Segment_Tree *&p,Segment_Tree *lst,int l,int r,int aim){  p=new Segment_Tree(),*p=*lst;  ++p->size;if(l==r)return;  if(aim<=mid)insert(p->ch[0],lst->ch[0],l,mid,aim);  else insert(p->ch[1],lst->ch[1],mid+1,r,aim);}inline int query(Segment_Tree *a,Segment_Tree *b,int l,int r,int z,int y){  if(z<=l&&r<=y)return b->size-a->size;  int ret=0;  if(z<=mid)ret+=query(a->ch[0],b->ch[0],l,mid,z,y);  if(mid
        
         ch[1],b->ch[1],mid+1,r,z,y);  return ret;}inline void dfs(int x){  L[x]=++Ti,dfn[Ti]=x;  for(int i=1;i
         
          =0;--i)    if(max[f[x][i]]>=len)      x=f[x][i];  return x;}inline bool check(int st,int len,int l,int r){  if(r-l+1