1009 失恋的小 T（后缀数组￥）

1009: 失恋的小 T

时间限制: 1 Sec  内存限制: 128 MB
提交: 160  解决: 76
[提交][状态][讨论版]

题目描述

小 T 最近失恋了，开始怀疑人生和爱情，他想知道在这世界中去伪存真后还剩多少。 
小 T 在网上拿到了代表大千世界的长字符串，删掉了所有换行空格和标点符号，只剩下了小写字母。 
现在字符串中有好多重复的子串，相同子串里只有一个是 Real 的。 
为了让小 T 走出失恋，你一定要告诉他这个世界上 Real 的东西有多少。 
（子串：串中任意个连续的字符组成的子序列称为该串的子串） 

输入

包含 100 组输入，每组为一行字符串，只包含小写字母，长度 1-5000。 

输出

输出 100 行，每行一个整数，对应输入的答案。 

样例输入

aaba

样例输出

8

提示

后缀数组，

我还不会，，

 #include<iostream>

 #include<stdio.h>

 #include<math.h>

 #include <string>

 #include<string.h>

 #include<map>

 #include<queue>

 #include<set>

 #include<utility>

 #include<vector>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define maxn 200100

 #define maxm 200005

 #define rd(x) scanf("%d", &x)

 #define rd2(x, y) scanf("%d%d", &x, &y)

 #define mod 1000000007

 const int MAXN = ;

 int t1[MAXN],t2[MAXN],c[MAXN];

 bool cmp(int *r, int a,int b,int l){

     return r[a] ==r[b] && r[a+l] == r[b+l];

 }

 void da(int str[], int sa[], int rankk[], int height[], int n, int m){

     n++;

     int i,j,p,*x =t1,*y=t2;

     for(i =; i <m; i++) c[i] =;

     for(i = ; i <n; i++) c[x[i] =str[i]]++;

     for(i =; i < m; i++) c[i] += c[i-];

     for(i = n-;i >= ; i--) sa[--c[x[i]]] = i;

     for(j =; j <= n; j <<=){

         p =;

         for(i = n-j; i <n; i++) y[p++] = i;

         for(i = ; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] -j;

         for(i = ; i < m; i++) c[i] =;

         for(i =  ;i < n; i++) c[x[y[i]]]++;

         for(i = ; i < m; i++) c[i] += c[i-];

         for(i = n-; i >=; i--) sa[--c[x[y[i]]]] = y[i];

         swap(x,y);

         p =; x[sa[]] =;

         for(int i = ; i < n; i++) x[sa[i]] = cmp(y, sa[i-], sa[i], j)?p-:p++;

         if(p >= n) break;

         m =p;

     }

     int k =;

     n--;

     for(i = ; i <= n;i++) rankk[sa[i]] = i;

     for(i = ; i < n;i++){

         if(k) k--;

         j =sa[rankk[i]-];

         while(str[i+k] == str[j+k]) k++;

         height[rankk[i]] = k;

     }

 }

 int rankk[MAXN],height[MAXN];

 char str[MAXN];

 int r[MAXN],sa[MAXN];

 int main()

 {

     int t = ;

     while(~scanf("%s", str)){

         //scanf("%s", str);

         int len = strlen(str);

         //int n = 2*len +1;

         for(int i =; i < len ;i++) r[i] = str[i];

         //for(int i =0; i < len; i++) r[len + 1 + i] = str[len -1 -i];

         r[len] =;

         r[len+] = ;

         da(r, sa, rankk, height,  len , 'z' + );

         long long int res = len - sa[];

         for(int i=  ;i <= len; i++){

             res = res + len - sa[i] -height[i];

         }

         printf("%lld\n", res);

     }

     return ;

 }