BZOJ 3172([Tjoi2013]單詞-後綴數組第一題+RMQ)

3172: [Tjoi2013]單詞
Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 268  Solved: 145
[Submit][Status]
Description
某人讀論文，一篇論文是由許多單詞組成。但他發現一個單詞會在論文中出現很多次，現在想知道每個單詞分別在論文
中出現多少次。

Input
第一個一個整數N,表示有多少個單詞，接下來N行每行一個單詞。每個單詞由小寫字母組成，N<=200,單詞長度不超過10^6

Output
輸出N個整數，第i行的數字表示第i個單詞在文章中出現了多少次。

Sample Input
3
a
aa
aaa

Sample Output
6
3
1

上一次寫RMQ是什麼時候？(喂，離題了）

好吧……

第一題後綴數組

不想寫下去了……（快哭了TNT)

這題在BZOJ上內存很容易開過（5人組-》TLE/CE/MLE/RE/AC）

大家要是這題RE把數組開小點。別忘了[RMQ*20]數組+數組之和 //省空間

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (300+10)
#define MAXL (1000200+10)
#define eps (1e-9)
typedef long long ll;
char s[MAXL];
int n,pre[MAXN],tai[MAXN];
int w[MAXL],sa[MAXL],wa[MAXL*2]={0},wb[MAXL*2]={0};
// x-->上一行 y->下一行sa右值   wv-->y的左值  sa-->上次排名(求) 
bool cmp(int *a,int x,int y,int l){return (a[x]==a[y]&&a[x+l]==a[y+l]);}
void suffix_array(int n,int m)
{
   int *x=wa,*y=wb;
   For(i,m) w[i]=0;
   For(i,n) w[x[i]=s[i]]++;
   Fork(i,2,m) w[i]+=w[i-1];
   ForD(i,n) sa[w[x[i]]--]=i;
   for(int j=1,p=0;p<n;j*=2,m=p)
   {
           
      p=0;
      Fork(i,n-j+1,n) y[++p]=i;
      For(i,n) if (j<sa[i]) y[++p]=sa[i]-j;
      
      For(i,m) w[i]=0;
      For(i,n) w[x[i]]++;
      For(i,m) w[i]+=w[i-1];
      
      
      ForD(i,n) sa[w[x[ y[i] ]]--]=y[i];
      //y is release
      
      p=y[sa[1]]=1;
      Fork(i,2,n)
         y[sa[i]]=(p+=(!cmp(x,sa[i-1],sa[i],j)));

      int *t=x;x=y;y=t;
   }
}
int height[MAXL],rank[MAXL]; //height[i] 表示 sa[i]與sa[i-1]的最長公共前綴 
void make_height(char *s,int n)
{
   For(i,n) rank[sa[i]]=i;
   For(i,n)
   {
      if (rank[i]==1) continue; //求height[rank[i]] 
      int j=max(0,height[rank[i-1]]-1),k=sa[rank[i]-1];
      while (s[i+j]==s[k+j]) j++;
      height[rank[i]]=j;
   }
}
int bin[MAXN]={0},f[MAXL][24]={0};
int lcp(int l,int r)
{
   int len=r-l+1,j=(int)log2(len);
   return min(f[l][j],f[r-bin[j]+1][j]);
}
int main()
{
// freopen("bzoj3172.in","r",stdin);
   scanf("%d",&n);pre[1]=1;
   For(i,n)
   {
      scanf("%s",s+pre[i]);
      tai[i]=strlen(s+pre[i]);
      s[pre[i]+tai[i]]='#';
      pre[i+1]=pre[i]+tai[i]+1;
   }
   s[pre[n+1]]=0;
   
   suffix_array(pre[n+1]-1,200);
   
   make_height(s,pre[n+1]-1);
   
   
   int logn=int(log2((double)pre[n+1]-1)+1);
   bin[0]=1;
   For(i,logn) bin[i]=bin[i-1]<<1;
   For(i,pre[n+1]-1) f[i][0]=height[i];
   
   For(j,logn)
      For(i,pre[n+1]-1-(1<<j)+1)
         f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
   
   For(i,n)
   {
      int tot=1;
      int j=rank[pre[i]]+1;
      {
         int l=2,r=j-1,ans=0;
         while (l<=r)
         {
            int m=l+r>>1;
            if (lcp(m,j-1)>=tai[i]) ans=m,r=m-1;
            else l=m+1;             
         }
         if (ans) ans=j-1-ans+1;
         tot+=ans;
      }
      {
         int l=j,r=pre[n+1]-1,ans=0;
         while (l<=r)
         {
            int m=l+r>>1;
            if (lcp(j,m)>=tai[i]) ans=m,l=m+1;
            else r=m-1;
         }
         if (ans) ans=ans-j+1;
         tot+=ans;
      }
      cout<<tot<<endl;
   }
// while (1);
   return 0;
}