World Final 2019 G. First of Her Name

发表于 | 阅读数

给一个名字的字典树，名字是尾读到根，求$t[i]$，是多少个名字的前缀之一。

将名字和$t$倒过就是求某个后缀出现次数。
建立广义$SAM$,即可。

  • 在线算法，需要注意在减少不必要的加点的时候也需要，也需要在已经成立的点的$siz$+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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

const int TN = 1e6 + 10;
struct Tri
{
    int son[TN][26], tcnt, fa[TN], c[TN];
    // void newnode()
    // {

    // }
    int insert(char s, int pre)
    {
        son[pre][s - 'A'] = ++tcnt;
        c[tcnt] = s;
        fa[tcnt] = pre;
        return tcnt;
    }
} tri;

const int SN = 2e6 + 100;
const int SM = 26;
struct SAM
{
    int trans[SN][SM], maxlen[SN], link[SN], scnt, siz[SN];
    queue<int> q;
    int pos[SN];
    SAM() { scnt = 1; };
    int insert(int id, int pre)
    {
        // if (trans[pre][id] && (maxlen[pre] + 1 == maxlen[trans[pre][id]]))
        //     return trans[pre][id];

        //bool flag = 0;
        int cur = ++scnt;

        maxlen[cur] = maxlen[pre] + 1;

        siz[cur] = 1;
        int u = pre, nc;
        //pre = cur;
        for (; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (maxlen[x] == maxlen[u] + 1)
                link[cur] = x;
            else
            {
                // if (u == pre)
                //     flag = 1;
                nc = ++scnt;
                maxlen[nc] = maxlen[u] + 1;
                link[nc] = link[x];
                link[cur] = link[x] = nc;
                memcpy(trans[nc], trans[x], sizeof(trans[x]));
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
            }
        }
        return cur;
    }
    void build()
    { //bfs遍历Trie树构造广义SAM

        for (int i = 0; i < 26; ++i)
            if (tri.son[0][i])
                q.push(tri.son[0][i]); //插入第一层字符

        pos[0] = 1; //Tire树上的根0在SAM上的位置为根1
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            //cout << x << ' ' << (tri.fa[x]) << endl;
            pos[x] = insert(tri.c[x] - 'A', pos[tri.fa[x]]); //注意是pos[Trie->fa[x]]
            for (int i = 0; i < 26; ++i)
                if (tri.son[x][i])
                    q.push(tri.son[x][i]);
        }
    }
} sam;

struct edge
{
    int to, nxt;
} e[SN];
int head[SN], ecnt;

void addadge(int u, int v)
{
    e[++ecnt].to = v;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
}

void dfs(int x)
{

    for (int i = head[x]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        dfs(e[i].to);
        sam.siz[x] += sam.siz[to];
    }
}
char t[N];
int ed[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        char ch[3];
        int op;
        scanf("%s %d", ch, &op);
        ed[i] = tri.insert(ch[0], ed[op]);
    }
    sam.build();
    for (int i = 2; i <= sam.scnt; i++)
        addadge(sam.link[i], i);
    dfs(1);

    for (int i = 1; i <= m; i++)
    {
        scanf("%s", t + 1);
        int len = strlen(t + 1);
        int u = 1;
        bool f = 1;
        for (int j = len; j >= 1; j--)
        {
            int id = t[j] - 'A';
            if (sam.trans[u][id])
                u = sam.trans[u][id];
            else
            {
                f = 0;
                break;
            }
        }
        //cout << f << endl;
        if (f)
            printf("%d\n", sam.siz[u]);
        else
            printf("0\n");
    }
}
在线算法 
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
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

const int TN = 1e6 + 10;

const int SN = 2e6 + 100;
const int SM = 26;
struct SAM
{
    int trans[SN][SM], maxlen[SN], link[SN], scnt, siz[SN];

    SAM() { scnt = 1; };
    int insert(int id, int pre)
    {
        if (trans[pre][id] && (maxlen[pre] + 1 == maxlen[trans[pre][id]]))
        {
            siz[trans[pre][id]] = 1;
            return trans[pre][id];
        }

        bool flag = 0;
        int cur = ++scnt;

        maxlen[cur] = maxlen[pre] + 1;

        siz[cur] = 1;
        int u = pre, nc;
        //pre = cur;
        for (; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (maxlen[x] == maxlen[u] + 1)
                link[cur] = x;
            else
            {
                if (u == pre)
                    flag = 1;
                nc = ++scnt;
                maxlen[nc] = maxlen[u] + 1;
                link[nc] = link[x];
                link[cur] = link[x] = nc;
                memcpy(trans[nc], trans[x], sizeof(trans[x]));
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
            }
        }
        return flag ? nc : cur;
    }

} sam;

struct edge
{
    int to, nxt;
} e[SN];
int head[SN], ecnt;

void addadge(int u, int v)
{
    e[++ecnt].to = v;
    e[ecnt].nxt = head[u];
    head[u] = ecnt;
}

void dfs(int x)
{

    for (int i = head[x]; i; i = e[i].nxt)
    {
        int to = e[i].to;
        dfs(e[i].to);
        sam.siz[x] += sam.siz[to];
    }
}
char t[N];
int ed[N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    ed[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        char ch[3];
        int op;
        scanf("%s %d", ch, &op);
        ed[i] = sam.insert(ch[0] - 'A', ed[op]);
    }

    for (int i = 2; i <= sam.scnt; i++)
        addadge(sam.link[i], i);
    dfs(1);

    for (int i = 1; i <= m; i++)
    {
        scanf("%s", t + 1);
        int len = strlen(t + 1);
        int u = 1;
        bool f = 1;
        for (int j = len; j >= 1; j--)
        {
            int id = t[j] - 'A';
            if (sam.trans[u][id])
                u = sam.trans[u][id];
            else
            {
                f = 0;
                break;
            }
        }
        //cout << f << endl;
        if (f)
            printf("%d\n", sam.siz[u]);
        else
            printf("0\n");
    }
}