untitled.cpp

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#include<cstdio>
#define N 500005
struct Node{
       vector<int>G;
       int parent,fail,len,belong,next,ok,ch;
}E[N];
const int Prime=599999;
int Hash[Prime+5];
int Bit[N],slen[N],T,n,len[N],S[N],S2[N],tot;
pair<int,int>tmp[N];
int BitSum(int Start,int x)
{
     int tmp=0;
     for(;x;x-=(x&(-x)))tmp+=Bit[Start+x];
     return tmp;
}
void BitModify(int Start,int End,int x,int value)
{
     for(;x+Start<=End;x+=(x&(-x)))Bit[Start+x]+=value;
}int AddCh(int P,int Ch,int belong,int pos)
{
     int hash=((P<<12)+Ch)%Prime;
     for(int i=Hash[hash];i;i=E[i].next)
        if(E[i].parent==P&&E[i].ch==Ch){
            if(belong&&pos==len[belong])E[i].ok=1;
            return i;
        }
     tot++;int i=Hash[hash];
     if(belong)
     {
      E[tot].parent=P;
      E[tot].ch=Ch;
      E[tot].belong=belong;
      E[tot].len=pos;
      E[tot].next=Hash[hash];
      Hash[hash]=tot;
      if(E[tot].len==len[belong])E[tot].ok=1;
      E[P].G.push_back(tot);
      return tot;
     }else return 0;
}
int Sp1[N],Sp2[N];
int Go(int P,int belong,int pos)
{
     while(Sp1[belong]+E[P].len<pos)
     {
         BitModify(slen[belong],slen[belong]+len[belong],S[Sp1[belong]+slen[belong]],-1);
         Sp1[belong]++;
     }while(Sp2[belong]<pos)
     {
         Sp2[belong]++;
         BitModify(slen[belong],slen[belong]+len[belong],S[Sp2[belong]+slen[belong]],1);
     }return AddCh(P,BitSum(slen[belong],S[slen[belong]+pos]-1),0,0);
}    
#include<queue>
queue<int>Q;     
void buildAc(){
     Q.push(1);
     while(!Q.empty())
     {
      int i=Q.front();Q.pop();
      if(i==1||E[i].parent==1)E[i].fail=1;
      else{
           int k,j=E[E[i].parent].fail;
           do{
               k=Go(j,E[i].belong,E[i].len);
               if(k==0)
               {
                       if(j==1)k=1;
                       else j=E[j].fail;
               }
           }while(k==0);
           E[i].fail=k;
      }if(E[E[i].fail].ok)E[i].ok=1;
      for(int j=0;j<E[i].G.size();j++)
      {
              Q.push(E[i].G[j]);
      }
     }
}  
int getint(){
     char ch;int tmp=0;
     for(ch=getchar();(ch<'0'||ch>'9');ch=getchar());
     for(;ch<='9'&&ch>='0';ch=getchar())tmp=tmp*10+ch-'0';
     return tmp;
}void print(int u){
      if(u<10)putchar(u+'0');
      else{
           print(u/10);
           putchar(u%10+'0');     
          }
}
int main(){
    T=getint();
    while(T--)
    {
              memset(Bit,0,sizeof(Bit));
              memset(Hash,0,sizeof(Hash));
              tot=Hash[0]=1;n=0;
              n=getint();
              for(int i=1;i<=n;i++)
              {
                      Sp1[i]=1;Sp2[i]=0;
                      slen[i]=slen[i-1]+len[i-1];
                      len[i]=getint();
                      for(int j=1;j<=len[i];j++)
                              tmp[j]=make_pair(getint(),j);
                      sort(tmp+1,tmp+1+len[i]);
                      for(int j=1;j<=len[i];j++)
                              S[slen[i]+tmp[j].second]=j;
              }
              for(int i=2;i<=n;i++)
              {
                      int k=1;
                      for(int j=1;j<=len[i];j++)
                      {
                              k=AddCh(k,BitSum(slen[i],S[slen[i]+j]-1),i,j);
                              BitModify(slen[i],slen[i]+len[i],S[slen[i]+j],1);
                      }
              }
              memset(Bit,0,sizeof(Bit));
              buildAc();
              int j=1;
              for(int i=1;i<=len[1];i++)
              {       
                      int k;
                      do{
                         k=Go(j,1,i);
                         if(k==0){
                                  if(j==1)k=1;
                                  else j=E[j].fail;
                         }
                      }while(k==0);
                      j=k;
                      if(E[j].ok)print(i),puts("");
              }
    }
}