[BZOJ2746][HEOI2012]旅行问题(AC自动机,树链剖分)

发布于 2018-03-24  68 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2746][HEOI2012]旅行问题(AC自动机,树链剖分)

Description

yz是Z国的领导人,他规定每个地区的名字只能为26个小写拉丁字母的一个。由于地 区数有可能超过26个,便产生了一个问题,如何辨别名字相同的地区?于是yz规定,一个 地区的描述必须包含它的所有上级,且上级按次序排列。于是,一个地区的描述是一个字符 串。比如说,一个地区的名字为c,它的上级为b,b的上级为a,a没有上级,那么这个地 区就描述为abc。显然,这个描述同时包含了c的上级b和b的上级a的描述,分别为ab和a。 值得注意的是,每个地区最多有一个上级,同一上级的地区之间名字不同,没有上级的 地区之间名字不同。现在,yz对外公布了n个地区的描述,这些描述中包含了Z国所有地区的描述,并让 你处理来访者的旅行问题。现有m对人访问这个国家,对于每对人,第一个人喜欢第i个描述中的第j个地区,设 这个地区描述为s1,第二个人喜欢第k个描述中的第l个地区,设这个地区描述为s2。他们为了统一行程,决定访问描述为s的地区(显然他们只关心地区的名字,并非是地区本身), 设s的长度为t,s需要满足以下条件:
1:t<=j, t<=l;
1:s[1..t] = s1[j-t+1 … j], s[1..t] = s2[l-t+1 … l];(即s为s1中1到k位 与s2中1到l位的公共后缀)
2:t最大化。
为了不使输出过大,你只需把这个字符串按照如下生成的26进制数转成10进制后mod 1000000007后输出:
a->0
b->1
.
.
.
z->25
比如地区cab被编码成2 * 26? + 0 * 26? + 1 * 26? = 1353。

Tag

AC自动机,树链剖分

解决思路

题目前面的部分其实就是告诉你这是一棵Trie树。
问题转化为给定若干个字符串,现在有若干组询问,对于询问 a,b,c,d,求第 a 个字符串长度为 b 的前缀,与第 c 个字符串长度为 d 的前缀的最长公共后缀,并且要求这个最长公共后缀是给出的字符串集中某一个字符串的前缀,输出对应的hash 值。
如果只是要求两个前缀的最长公共后缀,应该是可以用后缀数组解决的,转化为求两个后缀的最长公共前缀。但此题的问题在于,还要求这个公共后缀是字符串集中某一个字符串的前缀。
转化一下,既然这个公共后缀是某一个字符串的前缀,那么这两个后缀都应该能够匹配到这个前缀。
换句话说,如果是在 Fail 树中考虑这个问题,那么从这个两个后缀的结尾对应的节点开始跳 Fail 指针,要求都能跳到这个公共的前缀的结尾对应的节点。
所以,由于要求最长,问题就变成了在 Fail 树上求两点的 lca 了。这个可以用倍增、树链剖分等方式解决。
至于题目要求输出 hash 值,可以在插入 Trie 树的时候一并计算。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1000200;
const int maxAlpha=26;
const int Mod=1000000007;
const int hashbase=26;
const int inf=2147483647;

class TrieData
{
public:
    int fail;
    ll hash;
    int son[maxAlpha];
};

int n,nodecnt;
char str[maxN];
TrieData T[maxN];
vector<int> Pos[maxN];
int edgecnt=0,Head[maxN],Next[maxN],V[maxN];
int Hson[maxN],Size[maxN],Top[maxN],Fa[maxN],Depth[maxN];
queue<int> Queue;

void Insert(char *str,int id);
void GetFail();
void Add_Edge(int u,int v);
void dfs1(int u);
void dfs2(int u,int top);
int GetLCA(int u,int v);

int main()
{
    mem(Head,-1);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        Insert(str,i);
    }
    GetFail();//构建AC自动机Fail指针,同时建出Fail树
    dfs1(0);dfs2(0,0);//在Fail树上树链剖分
    int m;
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
        int u=Pos[a][b],v=Pos[c][d];//得到lca
        int lca=GetLCA(u,v);
        printf("%lld\n",(T[lca].hash+Mod)%Mod);
    }
    return 0;
}

void Insert(char *str,int id)
{
    int len=strlen(str+1);
    int now=0;
    Pos[id].push_back(0);
    for (int i=1;i<=len;i++)
    {
        if (T[now].son[str[i]-'a']==0) T[now].son[str[i]-'a']=++nodecnt,T[nodecnt].hash=((ll)T[now].hash*(ll)hashbase%Mod+str[i]-'a')%Mod;
        now=T[now].son[str[i]-'a'];
        Pos[id].push_back(now);
    }
    return;
}

void GetFail()
{
    for (int i=0;i<maxAlpha;i++) if (T[0].son[i]) Queue.push(T[0].son[i]);
    while (!Queue.empty())
    {
        int u=Queue.front();Queue.pop();
        for (int i=0;i<maxAlpha;i++)
            if (T[u].son[i])
            {
                T[T[u].son[i]].fail=T[T[u].fail].son[i];
                Queue.push(T[u].son[i]);
            }
            else T[u].son[i]=T[T[u].fail].son[i];
    }
    for (int i=1;i<=nodecnt;i++) Add_Edge(T[i].fail,i);
    return;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs1(int u)
{
    Size[u]=1;Hson[u]=-1;
    for (int i=Head[u];i!=-1;i=Next[i])
    {
        Fa[V[i]]=u;Depth[V[i]]=Depth[u]+1;dfs1(V[i]);
        Size[u]+=Size[V[i]];
        if ((Hson[u]==-1)||(Size[V[i]]>Size[Hson[u]])) Hson[u]=V[i];
    }
    return;
}

void dfs2(int u,int top)
{
    Top[u]=top;
    if (Hson[u]==-1) return;
    dfs2(Hson[u],top);
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=Hson[u]) dfs2(V[i],V[i]);
    return;
}

int GetLCA(int u,int v)
{
    while (Top[u]!=Top[v])
    {
        if (Depth[Top[u]]<Depth[Top[v]]) swap(u,v);
        u=Fa[Top[u]];
    }
    if (Depth[u]>Depth[v]) swap(u,v);
    return u;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2746][HEOI2012]旅行问题(AC自动机,树链剖分)


HNCJ OIer