【HDOJ5558】Alice'sClassifiedMessage（后缀数组）

  1 #include
  2 #include
  3 #include
  4 #include
  5 typedef long long ll;
  6 using namespace std;
  7 #define N   110000 
  8 #define oo  10000000
  9 #define MOD 100000073
 10 
 11 
 12 char ch[N];
 13 int n,i,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],Rank[N],pre[N],nxt[N];
 14 
 15 bool cmp(int *r,int a,int b,int l)
 16 {
 17     return r[a]==r[b]&&r[a+l]==r[b+l];
 18 }
 19 
 20 void getsa(int *r,int *sa,int n,int m)
 21 {
 22     int *x=wa,*y=wb,j,p;
 23     for(i=0;i;
 24     for(i=1;i1];
 25     for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i;
 26     for(j=1,p=1;p2,m=p)
 27     {
 28         p=0;
 29         for(i=n-j;ii;
 30         for(i=0;i)
 31          if(sa[i]>=j) y[p++]=sa[i]-j;
 32         for(i=0;ix[y[i]];  
 33         for(i=0;i0;
 34         for(i=0;i;
 35         for(i=1;i1];
 36         for(i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i];
 37         swap(x,y);
 38         p=1; x[sa[0]]=0;
 39         for(i=1;i1],sa[i],j)?p-1:p++;
 40         if(j>n) break; 
 41     } 
 42 }
 43 
 44 void getheight(int *r,int *sa,int n)
 45 {
 46     int i,j,k=0;
 47     for(i=1;i<=n;i++) Rank[sa[i]]=i;
 48     for(i=0;ik)
 49     {
 50         if(k) k--;
 51         j=sa[Rank[i]-1];
 52         while(r[i+k]==r[j+k]) k++;
 53     }
 54 }
 55 
 56 void init()
 57 {    
 58         memset(s,0,sizeof(s));
 59         memset(sa,0,sizeof(sa));
 60         memset(wa,0,sizeof(wa));
 61         memset(wb,0,sizeof(wb));
 62         memset(wc,0,sizeof(wc));
 63         memset(wd,0,sizeof(wd));
 64         memset(height,0,sizeof(height));
 65         memset(Rank,0,sizeof(Rank));
 66 }
 67 
 68 int main()
 69 { 
 70     int cas; 
 71     scanf("%d",&cas);
 72     for(int v=1;v<=cas;v++)
 73     {
 74         init();
 75         printf("Case #%d:\n",v);
 76         scanf("%s",ch);
 77         n=strlen(ch);
 78         for(int i=0;i'a'+1;
 79         s[n]=0;
 80         getsa(s,sa,n+1,100);
 81         getheight(s,sa,n);
 82         for(int i=1;i<=n;i++)
 83          if(!height[i]) pre[i]=i;
 84           else pre[i]=pre[i-1];
 85         for(int i=n;i>=1;i--)
 86          if(height[i+1]==0||i==n) nxt[i]=i;
 87           else nxt[i]=nxt[i+1];
 88         int i=0;
 89         while(i<n)
 90         {
 91             int now=Rank[i];
 92             int k=0; 
 93             int t=i;
 94             int mn=height[now];
 95             for(int j=now-1;j>=pre[now];j--)
 96             {
 97                 mn=min(mn,height[j+1]);
 98                 if(mnbreak;
 99                 if(sa[j]<i)
100                 {
101                     if(mn>k||mn==k&&sa[j]<t)
102                     {
103                         k=mn; t=sa[j];
104                     }
105                 }
106             }
107             if(now+1<=nxt[now]) mn=height[now+1];
108             for(int j=now+1;j<=nxt[now];j++)
109             {
110                 mn=min(mn,height[j]);
111                 if(mnbreak;
112                 if(sa[j]<i)
113                 {
114                     if(mn>k||mn==k&&sa[j]<t)
115                     {
116                         k=mn; t=sa[j];
117                     }
118                 }
119             }
120             if(!k)
121             {
122                 printf("-1 %d\n",ch[i]);
123                 i++;
124             }
125              else
126              {
127                  printf("%d %d\n",k,t);
128                  i+=k;
129              }
130         }        
131     }
132     return 0;
133 }
134