CF235C. Cyclical Quest

发表于 | 阅读数

给原串，和若干个询问串。求原串里有多少个不同子串可以通过询问串循环移动得到。

循环串只需要$s[i+len]=s[i]$,然后$LCS$匹配，然后尽力往上跳使得$\geq len$ ,因为这样$endpos$最大。
而且需要循环会重复，所以每次可以标记下匹配到那里。下次如果还是哪里就不用重复计算了。

代码 
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

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

const int SN = 2e6 + 10;
const int SM = 26;
struct SAM
{
    int trans[SN][SM], link[SN], pre, scnt, maxlen[SN], siz[SN];
    SAM() { pre = scnt = 1; }
    void insert(int id)
    {
        int cur = ++scnt;
        int u = pre;
        siz[cur] = 1;
        maxlen[cur] = maxlen[pre] + 1;
        for (; u && !trans[u][id]; u = link[u])
            trans[u][id] = cur;
        pre = cur;
        if (!u)
            link[cur] = 1;
        else
        {
            int x = trans[u][id];
            if (maxlen[x] == maxlen[u] + 1)
                link[cur] = x;
            else
            {
                int nc = ++scnt;
                maxlen[nc] = maxlen[u] + 1;
                link[nc] = link[x];
                memcpy(trans[nc], trans[x], sizeof(trans[x]));
                for (; u && trans[u][id] == x; u = link[u])
                    trans[u][id] = nc;
                link[cur] = link[x] = nc;
            }
        }
    }
} 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(to);
        sam.siz[x] += sam.siz[to];
    }
}
char s[N];
int vis[N];
int main()
{
    scanf("%s", s);
    int len = strlen(s);
    for (int i = 0; i < len; i++)
        sam.insert(s[i] - 'a');
    for (int j = 2; j <= sam.scnt; j++)
        addadge(.link[j], j);
    dfs(1);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        scanf("%s", s + 1);
        len = strlen(s + 1);
        for (int i = 1; i <= len; i++)
            s[i + len] = s[i];
        int u = 1;
        int lc = 0;
        int ans = 0;
        //cout << q << endl;
        for (int i = 1; i <= 2 * len; i++)
        {
            int id = s[i] - 'a';
            while (u && !sam.trans[u][id])
                u = sam.link[u], lc = sam.maxlen[u];
            if (!u)
            {
                u = 1;
                lc = 0;
                continue;
            }
            u = sam.trans[u][id], lc++;
            int p = u;
            int ll = lc;
            while (p && sam.maxlen[sam.link[p]] >= len)
                p = sam.link[p], ll = sam.maxlen[p];
            if (ll >= len && vis[p] != q + 1)
            {
                ans += sam.siz[p];
                vis[p] = q + 1;
            }
        }

        printf("%d\n", ans);
    }
}