【luoguP4600】[HEOI2012]旅行问题

这个题……tm是个语文阅读题吧。

翻译成人话就是,现在给定两个串,取他们的前缀,设这两个前缀分别为a,b,要求出一个最长的后缀,且这个后缀一定作为过某个字符串的前缀出现过。

仔细思考下……这tm不是建一个ac自动机然后fail树求lca吗

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;  
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = - x;
}

const int ms = (1 << 20), mo = 1e9 + 7;

int n, m, la, lb, lc, ld, pos[ms << 1], len[ms], ta, Q[ms];

char s[ms];

struct Acam
{
    int ch[ms][26], ne[ms], de[ms], tot, cnt, head[ms], ha[ms], tp[ms], sz[ms], son[ms], fa[ms];

    inline void insert(int l)
    {
        int no = 0;
        for(ri i = 0; i < l; i ++)
        {
            if(!ch[no][s[i] - 'a'])
                ch[no][s[i] - 'a'] = ++ cnt, ha[ch[no][s[i] - 'a']] = (26ll * ha[no] + s[i] - 'a') % mo;
            no = ch[no][s[i] - 'a'], pos[++ ta] = no;
        }
    }

    inline void init()
    {
        re(n); int Len;
        for(ri i = 1; i <= n; i ++)
            scanf("%s", s), Len = strlen(s), len[i] = len[i - 1] + Len, insert(Len);
    }

    struct in
    {
        int to, ne;
    }ter[ms << 1];

    inline void Build(int f, int l)
    {
        ter[++ tot] = (in){l, head[f]}, head[f] = tot;
        ter[++ tot] = (in){f, head[l]}, head[l] = tot;
    }

    void dfs1(int no)
    {
        de[no] = (no != 0) ? de[fa[no]] + 1 : 1, sz[no] = 1;
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no])
                continue;
            fa[to] = no, dfs1(to), sz[no] += sz[to];
            if((!son[no]) || (sz[son[no]] < sz[to]))
                son[no] = to;
        }
    }

    void dfs2(int no, int t)
    {
        tp[no] = t;
        if(son[no])
            dfs2(son[no], t);
        for(ri i = head[no]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(to == fa[no] || to == son[no])
                continue;
            dfs2(to, to);
        }
    }

    inline int lca(int x, int y)
    {
        while(tp[x] ^ tp[y])
            de[tp[x]] >= de[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
        return de[x] <= de[y] ? x : y;  
    }

    inline void build()
    {
        memset(head, -1, sizeof(int) * (cnt + 1)), tot = -1;
        int h1 = 0, t1 = -1;
        for(ri i = 0; i < 26; i ++)
            if(ch[0][i])
                Q[++ t1] = ch[0][i];
        while(h1 <= t1)
        {
            int qaq = Q[h1 ++]; Build(qaq, ne[qaq]);
            for(ri i = 0; i < 26; i ++)
            {
                if(ch[qaq][i])
                    ne[ch[qaq][i]] = ch[ne[qaq]][i], Q[++ t1] = ch[qaq][i];
                else
                    ch[qaq][i] = ch[ne[qaq]][i];
            }
        }
        fa[0] = -1, dfs1(0), dfs2(0, 0);
    }
}acam;

int main()
{
    acam.init(), acam.build();
    re(m);
    while(m --)
    {
        re(la), re(lb), re(lc), re(ld);
        int p1 = pos[len[la - 1] + lb], p2 = pos[len[lc - 1] + ld];
        //cout << p1 << ' ' << p2 << ' ' << acam.lca(p1, p2) << '\n';
        printf("%d\n", acam.ha[acam.lca(p1, p2)]);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注