目录

SP705-SUBST1 - New Distinct Substrings

2020-12-30 约 535 字预计阅读 2 分钟次阅读

目录

SP705-SUBST1 - New Distinct Substrings

题目:

题目描述:

Given a string, we need to find the total number of its distinct substrings.

输入格式:

T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000

输出格式:

For each test case output one number saying the number of distinct substrings.

样例:

样例输入1:

1
2
3
2
CCCCC
ABABA

样例输出1:

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Problem: SP705 SUBST1 - New Distinct Substrings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP705
// Memory Limit: 1.46 MB
// Time Limit: 280 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
const int maxn = 5e4 + 10;
char s[maxn];
int sa[maxn], rnk[maxn], tp[maxn];
int n, m;
int h[maxn];
int height[maxn];
void Tsort()
{
    for (int i = 0; i <= m; i++)
        h[i] = 0;
    for (int i = 1; i <= n; i++)
        h[rnk[i]]++;
    for (int i = 1; i <= m; i++)
        h[i] += h[i - 1];
    for (int i = n; i; i--)
        sa[h[rnk[tp[i]]]--] = tp[i];
}
void Ssort()
{
    m = 256;
    for (int i = 1; i <= n; i++)
        rnk[i] = s[i], tp[i] = i;
    Tsort();
    for (int w = 1, p = 0; p < n; w <<= 1, m = p)
    {
        p = 0;
        for (int i = 1; i <= w; i++)
            tp[++p] = n - w + i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > w)
                tp[++p] = sa[i] - w;
        Tsort();
        for (int i = 1; i <= n; i++)
            tp[i] = rnk[i];
        rnk[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++)
            rnk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;
    }
}
void Gh()
{
    int j, k;
    j = k = 0;
    for (int i = 1; i <= n; height[rnk[i++]] = k)
        for (k = k ? k - 1 : k, j = sa[rnk[i] - 1]; s[i + k] == s[j + k]; k++)
            ;
}
void solve()
{
    memset(h, 0, sizeof(h));
    memset(tp, 0, sizeof(h));
    memset(rnk, 0, sizeof(h));
    memset(height, 0, sizeof(h));

    Ssort();
    Gh();
    long long ans = (long long)(n + 1) * n / 2;
    for (int i = 1; i <= n; i++)
        ans -= height[i];
    yout << ans << endl;
}
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        cin >> (s + 1);
        n = strlen(s + 1);
        solve();
    }
    return 0;
}