洛谷P2408 不同子串个数 题解

题目链接：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;
}

本题有多倍经验。不过下面这俩题都是多测。

1. SP705 SUBST1 - New Distinct Substrings
2. SP694 DISUBSTR - Distinct Substrings

---

参考文献：

[1] https://www.luogu.com.cn/article/8hj9qxpo

---

题外话：

怎么会和 P3181 搞混的？