CF235C Cyclical Quest

题目描述

Some days ago, WJMZBMR learned how to answer the query "how many times does a string $ x $ occur in a string $ s $ " quickly by preprocessing the string $ s $ . But now he wants to make it harder.

So he wants to ask "how many consecutive substrings of $ s $ are cyclical isomorphic to a given string $ x $ ". You are given string $ s $ and $ n $ strings $ x_{i} $ , for each string $ x_{i} $ find, how many consecutive substrings of $ s $ are cyclical isomorphic to $ x_{i} $ .

Two strings are called cyclical isomorphic if one can rotate one string to get the other one. 'Rotate' here means 'to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order'. For example, string "abcde" can be rotated to string "deabc". We can take characters "abc" from the beginning and put them at the end of "de".

题意翻译

给一个主串和多个询问串,求主串有多少个子串与询问串循环同构。

输入格式

The first line contains a non-empty string $ s $ . The length of string $ s $ is not greater than $ 10^{6} $ characters.

The second line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of queries. Then $ n $ lines follow: the $ i $ -th line contains the string $ x_{i} $ — the string for the $ i $ -th query. The total length of $ x_{i} $ is less than or equal to $ 10^{6} $ characters.

In this problem, strings only consist of lowercase English letters.

输出格式

For each query $ x_{i} $ print a single integer that shows how many consecutive substrings of $ s $ are cyclical isomorphic to $ x_{i} $ . Print the answers to the queries in the order they are given in the input.

样例输入

baabaabaaa
5
a
ba
baa
aabaa
aaba

样例输出

7
5
7
3
5

分析

简单的想法就是建出SAM,然后找出询问串的每个循环同构串在SAM上对应的状态(如果存在的话),求right集合大小之和。

设主串为$s$,询问串为$p$,长度为$n$。先把$p$的前$n-1$个字符复制一份连接到$p$后面,然后把$p$在SAM上跑匹配。按正常的匹配方法,在做完$p$的前$i$个字符后,我们可以找到【在$p$中以位置$i$结尾的且在$s$中出现过的最长的串】所对应的状态$u$。若$max(u)\ge n$,说明以$i$结尾的循环同构串在$s$中有出现。但这个循环同构串还不一定在这个状态中,若$min(u)>n$,则令$u=fa(u)$,直到$min(u)\le n$,则把此时状态$u$的right集合大小记入答案。

另外,为了避免重复统计,一个节点只能被统计进答案一次,要开个$vis$数组判一下。

代码

#include <bits/stdc++.h>

const int N = 1e6+50;
const int SIZ = N << 1;

struct Sam {
    int top, last;
    int ch[SIZ][26], fa[SIZ], mx[SIZ], rcnt[SIZ];
    int buc[N], id[SIZ];

    Sam(): top(1), last(1) {}

    void extend(char c) {
        int x = c - 'a', p = last;
        int np = last = ++top;
        mx[np] = mx[p] + 1;
        rcnt[np] = 1;
        for (; p && !ch[p][x]; p = fa[p])
            ch[p][x] = np;
        if (!p) {
            fa[np] = 1;
            return;
        }
        int q = ch[p][x];
        if (mx[q] == mx[p] + 1) {
            fa[np] = q;
            return;
        }
        int nq = ++top;
        mx[nq] = mx[p] + 1;
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof ch[nq]);
        for (; ch[p][x] == q; p = fa[p])
            ch[p][x] = nq;
    }

    void work() {
        for (int i = 1; i <= top; i++)
            buc[mx[i]]++;
        for (int i = 1; i <= top; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i <= top; i++)
            id[buc[mx[i]]--] = i;

        for (int i = top; i >= 2; i--) {
            int u = id[i];
            rcnt[fa[u]] += rcnt[u];
        }
    }
} sam;

char s[N], p[N<<1];
int vis[SIZ];

int main() {
    scanf("%s", s);
    int n = strlen(s), m;
    for (int i = 0; i < n; i++)
        sam.extend(s[i]);
    sam.work();

    scanf("%d", &m);
    for (int cas = 1; cas <= m; cas++) {
        scanf("%s", p);
        int lp = strlen(p);
        memcpy(p+lp, p, lp-1);
        int u = 1, len = 0, ans = 0;
        for (int i = 0; i < lp*2-1; i++) {
            int x = p[i] - 'a';
            if (sam.ch[u][x]) {
                u = sam.ch[u][x];
                len++;
            } else {
                while (len && !sam.ch[u][x]) {
                    u = sam.fa[u];
                    len = sam.mx[u];
                } 
                if (sam.ch[u][x]) {
                    u = sam.ch[u][x];
                    len++;
                }
            }
            while (sam.mx[sam.fa[u]] >= lp) {
                u = sam.fa[u];
                len = sam.mx[u];
            }
            if (len >= lp && vis[u] != cas) {
                vis[u] = cas;
                ans += sam.rcnt[u];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论