Codeforces 235 C

题目大意

给定一个模板串, 再给出\(n\)个询问, 询问每一个串的循环串总共在原串中出现了多少次.

循环串: 比如说有\(str[] = \{ABCD\}\), 则其循环串有\(\{ABCD\}, \{BCDA\}, \{CDAB\}, \{DABC\}\), 共\(len\)个.

题解

把每一个串复制一遍放在原串后面: \(\{ABCD\} \to \{ABCDABC\}\), 放入原串的后缀自动机中匹配. 在匹配时, 假如下一位无法匹配, 则跳suffix link; 假如即使跳了suffix link, 最大长度\(len(suffix)\)仍然大于等于原串长度, 则也跳suffix link(相当于砍掉多余的部分).

放入SAM前要先跑一次KMP去循环节.

#include <cstdio>

#include <cstring>

#include <vector>

const int LEN = (int)1e6;

struct suffixAutomaton

{

    struct state

    {

        state *suc[26], *pre;

        int len;

        int sz, tg;

        std::vector<state*> bck;

        inline state()

        {

            for(int i = 0; i < 26; ++ i)

                suc[i] = NULL;

            pre = NULL;

            sz = 1;

            bck.clear();

            tg = 0;

        }

    };

    state *rt, *lst;

    inline void insert(int c)

    {

        state *u = new state;

        u->len = lst->len + 1;

        for(; lst != NULL && lst->suc[c] == NULL; lst->suc[c] = u, lst = lst->pre);

        if(lst == NULL)

            u->pre = rt;

        else

        {

            state *p = lst->suc[c];

            if(p->len == lst->len + 1)

                u->pre = p;

            else

            {

                state *q = new state;

                *q = *p;

                q->len = lst->len + 1, q->sz = 0;

                p->pre = u->pre = q;

                for(; lst != NULL && lst->suc[c] == p; lst->suc[c] = q, lst = lst->pre);

            }

        }

        lst = u;

    }

    void DFS(state *u)

    {

        u->tg = 1;

        if(u->pre != NULL)

            u->pre->bck.push_back(u);

        for(int i = 0; i < 26; ++ i)

            if(u->suc[i] != NULL && ! u->suc[i]->tg)

                DFS(u->suc[i]);

    }

    void get(state *u)

    {

        for(std::vector<state*>::iterator p = u->bck.begin(); p != u->bck.end(); ++ p)

            get(*p), u->sz += (*p)->sz;

    }

    inline void build(char *str, int len)

    {

        lst = rt = new state;

        rt->len = 0;

        for(int i = 0; i < len; ++ i)

            insert(str[i] - 'a');

        DFS(rt);

        get(rt);

    }

    inline int match(char *str, int len, int cir)

    {

        state *u = rt;

        int cur = 0;

        long long ans = 0;

        for(int i = 0; i < len + cir - 1; ++ i)

        {

            for(; u != rt && u->suc[str[i] - 'a'] == NULL; cur = u->pre->len, u = u->pre);

            if(u->suc[str[i] - 'a'] != NULL)

                u = u->suc[str[i] - 'a'], ++ cur;

            for(; u != rt && u->pre->len >= len; cur = u->pre->len, u = u->pre);

            if(cur >= len)

                ans += u->sz;

        }

        return ans;

    }

}SAM;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("CF235C.in", "r", stdin);

    #endif

    static char str[LEN];

    scanf("%s", str);

    int len = strlen(str);

    SAM.build(str, len);

    int n;

    scanf("%d\n", &n);

    for(int i = 0; i < n; ++ i)

    {

        static char str[LEN << 1];

        scanf("%s", str);

        int len = strlen(str);

        static int nxt[LEN];

        nxt[0] = -1;

        int p = nxt[0];

        for(int i = 1; i < len; ++ i)

        {

            for(; ~ p && str[i] ^ str[p + 1]; p = nxt[p]);

            nxt[i] = str[i] == str[p + 1] ? ++ p : p;

        }

        int cir = len % (len - nxt[len - 1] - 1) == 0 ? len - nxt[len - 1] - 1 : len;

        for(int i = 0; i < cir; ++ i)

            str[i + len] = str[i];

        printf("%d\n", SAM.match(str, len, cir));

    }

}

巴特西

Codeforces 235 C

题目大意

题解

最新文章

热门文章