嘘~ 正在从服务器偷取页面 . . .

洛谷P2408 不同子串个数题解

发布日期: 2024-06-08

更新日期: 2024-06-17

文章字数: 677

洛谷P2408 不同子串个数题解

题意：

给你一个长为 $n$ 的字符串，求本质不同的子串的个数。

输入格式：

第一行一个整数 $n$。

接下来一行 $n$ 个字符表示给出的字符串。

输出格式：

一行一个整数，表示不一样的子串个数。

数据范围：

保证 $1 \leq n \le 10^5$，字符串中只有小写英文字母。

不要把这题跟 P3181 搞混了，~~反正我自己搞混了~~

考虑构建后缀数组，那么对于排名为 $i$ 的后缀，它的贡献为 $n-\texttt{sa[i]}+1-\texttt{height[i]}$ 。

因为所有的后缀按字典序排序，不存在前缀 $S$ 不为 $\mathrm{LCP}(i-1,i)$ 却为 $\mathrm{LCP}(i-k,i)$ ，其中 $k > 1$ 。

所以这样计算贡献不重不漏。于是答案就是

$\frac{n(n+1)}{2} - \sum_{i=2}^n \texttt{height[i]}$

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 55))
#define mem(a) memset(a, 0, sizeof(a))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N];
int sa[N], rk[N * 2], tmp[N * 2], height[N], cnt[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getlcp(const int n)
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void init(const int n)
{
    const int m = max(n, 233);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
ll solve(const int n)
{
    init(n); getlcp(n); ll res = (ll)n * (n + 1) / 2;
    for(int i = 2; i <= n; i++) res -= height[i];
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n >> (s + 1); cout << solve(n) << '\n';
    return 0;
}