SPOJ SUBST1 New Distinct Substrings（后缀数组本质不同子串个数）题解

刺骨的言语ヽ痛彻心扉 2021-11-05 02:08 251阅读 0赞

# 题意： #

问给定串有多少本质不同的子串？

# 思路： #

子串必是某一后缀的前缀，假如是某一后缀\\(sa\[k\]\\)，那么会有\\(n - sa\[k\] + 1\\)个前缀，但是其中有\\(height\[k\]\\)个和上一个重复，那么最终的贡献的新串为\\(n - sa\[k\] + 1 - height\[k\]\\)。故最终结果为\\(\\sum\_\{i = 1\}^n (n - sa\[k\] + 1 - height\[k\])\\)，即 \\(\\frac\{n \* (n + 1)\}\{2\} - \\sum\_\{i = 1\}^nheight\[k\]\\)。

# 参考： #

[后缀数组——处理字符串的有力工具][Link 1]

# 代码： #

#include<map> #include<set> #include<queue> #include<cmath> #include<stack> #include<ctime> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 50000 + 5; const int INF = 0x3f3f3f3f; const ull seed = 11; const int MOD = 1e9 + 7; using namespace std; int str[maxn]; int t1[maxn], t2[maxn], c[maxn]; int sa[maxn]; int rk[maxn]; int height[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 n, int m){ n++; int i, j, p, *x = t1, *y = t2; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[i] = str[i]]++; for(i = 1; i < m; i++) c[i] += c[i - 1]; for(i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i; for(j = 1; j <= n; j <<= 1){ p = 0; for(i = n - j; i < n; i++) y[p++] = i; for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[y[i]]]++; for(i = 1; i < m; i++) c[i] += c[i - 1]; for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; for(i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++; if(p >= n) break; m = p; } int k = 0; n--; for(i = 0; i <= n; i++) rk[sa[i]] = i; for(i = 0; i < n; i++){ if(k) k--; j = sa[rk[i] - 1]; while(str[i + k] == str[j + k]) k++; height[rk[i]] = k; } } char s[maxn]; int main(){ int T; scanf("%d", &T); while(T--){ scanf("%s", s); int len = strlen(s); for(int i = 0; i < len; i++){ str[i] = s[i]; } s[len] = 0; da(str, len, 127); ll n = len; ll ans = n * (n + 1LL) / 2LL; for(int i = 1; i <= n; i++){ ans -= height[i]; } printf("%lld\n", ans); } return 0; }

转载于:https://www.cnblogs.com/KirinSB/p/11284973.html

[Link 1]: https://wenku.baidu.com/view/228caa45b307e87101f696a8.html