Codeforces 666E Forensic Examination

Codeforces 666E Forensic Examination
제목 대의: 원래 문자 S S, m 개의 일치 하 는 문자열 이 있 습 니 다. S [pl, pr] S [p l, p r] 라 는 문 자 는 [l, r] [l, r] 사이 에 있 는 문자열 중 가장 많은 횟수 가 있 는 것 이 무엇 이 냐 고 물 었 습 니 다. 몇 번 이나 나 타 났 습 니까? (최대 횟수 가 같 으 면 출력 번호 가 작은 것)
불완전 이해 + 해법 (접미사 자동 동기 + 선분 트 리 통합)
코드 에 이해
큰 문자열 의 일치 에 대해 우 리 는 S S 와 m 개의 문자열 을 연결 하 는 것 을 선택 한 후에 일치 하 는 문자열 이 right r i g h t 집합 에 나타 나 는 것 을 발견 할 수 있 습 니 다. 그래서 우 리 는 parent p a r e n t 트 리 를 추출 합 니 다.parent p a r e n t 에 대응 하 는 것 은 right r i g h t 집합 트 리 이기 때문에 parent p a r e n t 트 리 에 있 는 점 을 모두 해당 하 는 번 호 를 표시 하고 지속 가능 한 선분 트 리 로 기록 합 니 다.

               ：
          （                     ）      
                           

그리고 parent p a r n t 트 리 의 대응 관 계 를 합 쳐 코드 설명 을 구체 적 으로 보 세 요.
코드 + 주석 (코드 는 본인 이 쓴 것 이 아 닙 니 다. 아직 완전히 이해 하지 못 했 기 때 문 입 니 다)

#include
#define ll long long
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int M=24000005;
const int mxn=1200005;
char s[mxn];
int a,b,c,d,num,size,ans;
int cnt,m,T,p,q,np,nq,Q,tot,len;
int ls[M],rs[M],mx[M],id[M],B[mxn],C[mxn];
int color[mxn],pos[mxn],step[mxn],pre[mxn][24],son[mxn][28],root[mxn];

inline void update(int x)//    
{
    if(mx[ls[x]]==mx[x] && id[ls[x]]<id[x]) id[x]=id[ls[x]];
    if(mx[ls[x]]>mx[x]) mx[x]=mx[ls[x]],id[x]=id[ls[x]];
    if(mx[rs[x]]>mx[x]) mx[x]=mx[rs[x]],id[x]=id[rs[x]];
}

inline void insert(int &x,int l,int r,int v)//       
{
    if(!x) x=(++size);
    if(l==r) {mx[x]++,id[x]=l;return;}
    int mid=l+r>>1;
    if(v<=mid) insert(ls[x],l,mid,v);
    else insert(rs[x],mid+1,r,v);
    update(x);
}//           （         ），        （           ）

inline void find(int x,int l,int r,int L,int R)//    
{
    if(!x) return;
    if(L<=l && r<=R)
    {
        if(ansid[x];
        else if(ans==mx[x] && num>id[x]) num=id[x];
        return;
    }
    int mid=l+r>>1;
    if(R<=mid) find(ls[x],l,mid,L,R);
    else if(L>mid) find(rs[x],mid+1,r,L,R);
    else find(ls[x],l,mid,L,mid),find(rs[x],mid+1,r,mid+1,R);
}

inline int merge(int x,int y,int l,int r)//  
{
    if(!x||！y) return x|y;//          ，          
    int z=(++size),mid=l+r>>1;//    
    if(l==r)
    {
        mx[z]=mx[x]+mx[y];//                ，         
        id[z]=l;
        return z;
    }
    //           
    ls[z]=merge(ls[x],ls[y],l,mid);
    rs[z]=merge(rs[x],rs[y],mid+1,r);
    update(z);
    return z;
}

inline void sam(int w)//       ，w      ，       0
{
    int i,j,c;
    fo(i,1,len+1)
    {
        p=np;
        if(i==len+1) c=27;
        else c=s[i]-'a'+1;
        step[np=(++tot)]=step[p]+1;
        if(!w && i<=len) pos[i]=np;//          
        if(w && i<=len)  insert(root[np],1,cnt,w);//m         
        while(p && !son[p][c])
          son[p][c]=np,p=pre[p][0];//    parent    ，     pre[p][0]     1   
        if(!p) {pre[np][0]=1;continue;}
        q=son[p][c];
        if(step[q]==step[p]+1)
          pre[np][0]=q;
        else
        {
            step[nq=(++tot)]=step[p]+1;
            memcpy(son[nq],son[q],sizeof son[q]);
            pre[nq][0]=pre[q][0];
            pre[q][0]=pre[np][0]=nq;
            while(p && son[p][c]==q)
              son[p][c]=nq,p=pre[p][0];
        }
    }
}

inline void init()
{
    int i,j;
    fo(i,1,tot) B[step[i]]++;
    fo(i,1,tot) B[i]+=B[i-1];
    fo(i,1,tot) C[B[step[i]]--]=i;
    for(i=tot;i>=1;i--)
    {
        int x=C[i],fa=pre[x][0];// parent        
        root[fa]=merge(root[fa],root[x],1,cnt);//    ->        parent 
    }
    fo(j,1,22) fo(i,1,tot) pre[i][j]=pre[pre[i][j-1]][j-1];//parent    
}

int main()
{
    int i,j;
    scanf("%s",s+1);
    len=strlen(s+1);
    tot=np=1,sam(0);
    scanf("%d",&cnt);
    fo(i,1,cnt)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        sam(i);
    }
    init();
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d%d%d%d",&c,&d,&a,&b);
        len=b-a+1,b=pos[b];
        for(j=22;j>=0;j--)
          if(step[pre[b][j]]>=len)
            b=pre[b][j];//                
        ans=0,num=0,find(root[b],1,cnt,c,d);//         
        if(!ans) printf("%d %d
",c,0);
        else printf("%d %d
",num,ans);
    }
    return 0;
}