SPOJ 694&&SPOJ705: Distinct Substrings

时间：2021-05-14 04:45:12

DISUBSTR - Distinct Substrings

链接

题意：

　　询问有多少不同的子串。

思路：

　　后缀数组或者SAM。

　　首先求出后缀数组，然后从对于一个后缀，它有n-sa[i]-1个前缀，其中有height[rnk[i]]个被rnk[i]-1的后缀算了。所以再减去height[rnk[i]]即可。

代码：

换了板子。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 using namespace std;

 const int N = ;

 char s[N];

 int t1[N],t2[N],sa[N],height[N],rnk[N],c[N];

 int n;

 void get_sa(int m) {

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

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

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

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

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

     for (int k=; k<=n; k<<=) {

         p = ;

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

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

         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 (i=; i<=n; ++i)

             x[sa[i]] = y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k] ? p- : p++;

         if (p > n) break;

         m = p;

     }

 }

 void get_height() {

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

     int k = ;

     height[] = ;

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

         if (rnk[i]==) continue;

         if (k) k--;

         int j = sa[rnk[i]-];

         while (i+k<=n && j+k<=n && s[i+k]==s[j+k])

          k++;

         height[rnk[i]] = k;

     }

 }

 void get_ans() {

     long long ans = ;

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

         ans += max(n-i+-height[rnk[i]],);

 //      ans += max(n-sa[i]-height[i],0);

     }

     cout << ans << '\n';

 }

 int main() {

     int T;

     scanf("%d",&T);

     while (T--) {

         scanf("%s",s+);

         n = strlen(s+);

         get_sa();

         get_height();

         get_ans();

     }

     return ;

 }

原来的

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 using namespace std;

 const int N = ;

 char s[N];

 int t1[N],t2[N],sa[N],height[N],rnk[N],c[N];

 int n;

 void get_sa(int m) {

     int *x = t1,*y = t2;

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

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

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

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

     for (int k=; k<=n; k<<=) {

         int p = ;

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

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

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

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

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

         for (int 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]] = (y[sa[i-]]==y[sa[i]] && sa[i-]+k<n && sa[i]+k<n &&

             y[sa[i-]+k]==y[sa[i]+k]) ? p- : p++;

         if (p >= n) break;

         m = p;

     }

 }

 void get_height() {

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

     int k = ;

     height[] = ;

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

         if (!rnk[i]) continue;

         if (k) k--;

         int j = sa[rnk[i]-];

         while (i+k < n && j+k < n && s[i+k]==s[j+k]) k++;

         height[rnk[i]] = k;

     }

 }

 void get_ans() {

     long long ans = ;

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

         ans += max(n-i-height[rnk[i]],);

 //        ans += max(n-sa[i]-height[i],0);

     }

     cout << ans << '\n';

 }

 int main() {

     int T;

     scanf("%d",&T);

     while (T--) {

         scanf("%s",s);

         n = strlen(s);

         get_sa();

         get_height();

         get_ans();

     }

     return ;

 }

相关文章