【POJ】3415 Common Substrings

  1 #include<cstdio>
  2 #include<cstring>
  3 typedef __int64 LL;
  4 #define MAXN 200010
  5 char s[MAXN];
  6 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
  7 int sa[MAXN],height[MAXN],rk[MAXN];
  8 int stk[MAXN],cnt[MAXN];
  9 inline bool cmp(int *r,int a,int b,int len)
 10 {
 11     return r[a]==r[b]&&r[a+len]==r[b+len];
 12 }
 13 void SA(int n,int m)
 14 {
 15     int i,j,p,*x=wa,*y=wb,*t;
 16     for(i=0;i<m;i++)
 17         ws[i]=0;
 18     for(i=0;i<n;i++)
 19         ws[x[i]=s[i]]++;
 20     for(i=1;i<m;i++)
 21         ws[i]+=ws[i-1];
 22     for(i=n-1;i>=0;i--)
 23         sa[--ws[x[i]]]=i;
 24     for(j=p=1;p<n;j<<=1,m=p)
 25     {
 26         for(p=0,i=n-j;i<n;i++)
 27             y[p++]=i;
 28         for(i=0;i<n;i++)
 29         {
 30             if(sa[i]>=j)
 31                 y[p++]=sa[i]-j;
 32         }
 33         for(i=0;i<m;i++)
 34             ws[i]=0;
 35         for(i=0;i<n;i++)
 36             ws[wv[i]=x[y[i]]]++;
 37         for(i=1;i<m;i++)
 38             ws[i]+=ws[i-1];
 39         for(i=n-1;i>=0;i--)
 40             sa[--ws[wv[i]]]=y[i];
 41         for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)
 42             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 43     }
 44 }
 45 void Height(int n)
 46 {
 47     int i,j,k;
 48     for(i=1;i<=n;i++)
 49         rk[sa[i]]=i;
 50     for(i=k=0;i<n;height[rk[i++]]=k)
 51         for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
 52 }
 53 int main()
 54 {
 55     LL ans,temp;
 56     int k,len,n,i,top,size;
 57     while(scanf("%d",&k),k)
 58     {
 59         scanf(" %s",s);
 60         len=strlen(s);
 61         s[len]='#';
 62         scanf(" %s",s+len+1);
 63         n=strlen(s);
 64         SA(n+1,'z'+1);
 65         Height(n);
 66         for(i=1;i<=n;i++)
 67         {
 68             if(height[i]>=k)
 69                 height[i]-=k-1;
 70             else
 71                 height[i]=0;
 72         }
 73         ans=temp=0;
 74         top=-1;
 75         for(i=1;i<=n;i++)
 76         {
 77             for(size=0;top>-1&&stk[top]>height[i];top--)
 78             {
 79                 size+=cnt[top];
 80                 temp+=(height[i]-stk[top])*cnt[top];
 81             }
 82             stk[++top]=height[i];
 83             cnt[top]=size;
 84             if(sa[i-1]<len)
 85             {
 86                 temp+=height[i];
 87                 cnt[top]++;
 88             }
 89             if(sa[i]>len)
 90                 ans+=temp;
 91         }
 92         temp=0;
 93         top=-1;
 94         for(i=1;i<=n;i++)
 95         {
 96             for(size=0;top>-1&&stk[top]>height[i];top--)
 97             {
 98                 size+=cnt[top];
 99                 temp+=(height[i]-stk[top])*cnt[top];
100             }
101             stk[++top]=height[i];
102             cnt[top]=size;
103             if(sa[i-1]>len)
104             {
105                 temp+=height[i];
106                 cnt[top]++;
107             }
108             if(sa[i]<len)
109                 ans+=temp;
110         }
111         printf("%I64d\n",ans);
112     }
113     return 0;
114 }