Blackops

初心易得，始终难守

0%

HDU 6194 string string string（后缀自动机+parent树+性质理解）

发表于 分类于 ， ，

string string string

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2057 Accepted Submission(s): 624

Problem Description
Uncle Mao is a wonderful ACMER. One day he met an easy problem, but Uncle Mao was so lazy that he left the problem to you. I hope you can give him a solution.
Given a string s, we define a substring that happens exactly k times as an important string, and you need to find out how many substrings which are important strings.

Input
The first line contains an integer T (T≤100) implying the number of test cases.
For each test case, there are two lines:
the first line contains an integer k (k≥1) which is described above;
the second line contain a string s (length(s)≤105).
It’s guaranteed that ∑length(s)≤2∗106.

Output
For each test case, print the number of the important substrings in a line.

Sample Input
2
2
abcabc
3
abcabcabcabc

Sample Output
6
9

题目链接：HDU 6194
比赛那会儿没做出来，因为刚学$SA$性质也不太理解，更不要说用还没学的$SAM$做了，这题如果能知道$right$集合的意义还有$len$的意义就比较好写了。
这里有一个要利用的性质：同一个$right$集合内的子串长度从$L[u].len$按公差为$1$递减，那么对于任意一个节点$u$，如果以它作为接受态，那么它有$|right{u}|$个可能构成的后缀串其长度为连续的$L[L[u].pre].len+1…L[u].len$中的值。
那么我们按照$parent$树自下而上叠加$|right|$的大小，然后看$|right|$的大小，如果等于$k$则说明这个节点接受的子串集合均出现过$k$次，那么答案累加上$u$的管辖长度$L[u].len-L[L[u].pre].len$
代码：

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct Trie
{
    int nxt[26], pre, len, v;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        len = 0;
        v = 0;
        pre = -1;
    }
} L[N << 1];
int sz, last;
int node[N << 1], cnt[N];
char s[N];

void init()
{
    sz = last = 0;
    L[sz++].init();
    CLR(cnt, 0);
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int c)
{
    int u = newnode();
    L[u].len = L[last].len + 1;
    L[u].v = 1;
    int t = last;
    while (~t && L[t].nxt[c] == -1)
    {
        L[t].nxt[c] = u;
        t = L[t].pre;
    }
    if (t == -1)
        L[u].pre = 0;
    else
    {
        int v = L[t].nxt[c];
        if (L[t].len + 1 == L[v].len)
            L[u].pre = v;
        else
        {
            int np = newnode();
            L[np] = L[v];
            L[np].len = L[t].len + 1;
            L[np].v = 0;
            L[u].pre = L[v].pre = np;
            while (~t && L[t].nxt[c] == v)
            {
                L[t].nxt[c] = np;
                t = L[t].pre;
            }
        }
    }
    last = u;
}
int main(void)
{
    int TC, k, i;
    scanf("%d", &TC);
    while (TC--)
    {
        init();
        scanf("%d%s", &k, s);
        int len = strlen(s);
        for (i = 0; i < len; ++i)
            ins(s[i] - 'a');
        for (i = 0; i < sz; ++i)
            ++cnt[L[i].len];
        for (i = 1; i <= len; ++i)
            cnt[i] += cnt[i - 1];
        for (i = sz - 1; i >= 0; --i)
            node[--cnt[L[i].len]] = i;
        for (i = sz - 1; i >= 0; --i)
        {
            int u = node[i];
            if (~L[u].pre)
                L[L[u].pre].v += L[u].v;
        }
        LL ans = 0;
        for (i = 0; i < sz; ++i)
            if (L[i].v == k)
                ans += L[i].len - L[L[i].pre].len;
        printf("%I64d\n", ans);
    }
    return 0;
}