F - New Distinct Substrings （后缀数组）

题目链接：https://cn.vjudge.net/contest/283743#problem/F

题目大意：给你一个字符串，然后让你求出不同的子串的个数。

具体思路：首先，一个字符串中总的子串个数是len*(len+1)/2,然后就开始去重了，通过height数组，求出所有重复的子串的个数，然后就用总的子串的个数-重复的子串的个数就可以了。

AC代码：

 #include<iostream>

 #include<stack>

 #include<cstring>

 #include<iomanip>

 #include<stdio.h>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 # define ll long long

 const int maxn = 5e5+;

 int cntA[maxn], cntB[maxn], sa[maxn], tsa[maxn], A[maxn], B[maxn], height[maxn];

 int Rank[maxn];

 char ch[maxn];

 ll n;

 //sa[i]代表第i小的后缀位置，Rank[i]代表第i位置开始的后缀在所有的后缀串中排名第几

 // height[i]代表排名第i个字符串和第i-1个字符串的相同前缀的长度

 void cal()

 {

     for(int i = ; i < ; i++) cntA[i] = ;

     for(int i = ; i <= n; i++) cntA[ch[i-]]++;

     for(int i = ; i < ; i++) cntA[i] += cntA[i-];

     for(int i = n; i; i--) sa[cntA[ch[i-]]--] = i;

     Rank[sa[]] = ;

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

     {

         Rank[sa[i]] = Rank[sa[i-]];

         if(ch[sa[i]-] != ch[sa[i-]-]) Rank[sa[i]]++;

     }

     for(int l = ; Rank[sa[n]] < n; l <<= )

     {

         memset(cntA, , sizeof(cntA));

         memset(cntB, , sizeof(cntB));

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

         {

             cntA[A[i] = Rank[i]]++;

             cntB[B[i] = (i+l <= n)?Rank[i+l]:]++;

         }

         for(int i = ; i <= n; i++) cntB[i] += cntB[i-];

         for(int i = n; i; i--) tsa[cntB[B[i]]--] = i;

         for(int i = ; i <= n; i++) cntA[i] += cntA[i-];

         for(int i = n; i; i--) sa[cntA[A[tsa[i]]]--] = tsa[i];

         Rank[sa[]]=;

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

         {

             Rank[sa[i]] = Rank[sa[i-]];

             if(A[sa[i]] != A[sa[i-]] || B[sa[i]] != B[sa[i-]]) Rank[sa[i]]++;

         }

     }

     for(int i = , j = ; i <= n; i++)

     {

         if(j) j--;

         while(ch[i+j-] == ch[sa[Rank[i]-] + j - ]) j++;

         height[Rank[i]] = j;

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%s",ch);

        n=strlen(ch);

         if(n==)

         {

             printf("1\n");

             continue;

         }

         // cout<<1<<endl;

         cal();

         ll ans=n*(n+)/;

         //cout<<ans<<endl;

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

         {

             ans-=height[i];

          // cout<<i<<" "<<height[i]<<endl;

         }

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

     }

     return ;

 }

巴特西

F - New Distinct Substrings （后缀数组）

最新文章

热门文章