[HDU5469]Antonidas(点分治,字符串Hash)

发布于 2018-02-26  146 次阅读


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

本文链接地址:[HDU5469]Antonidas(点分治,字符串Hash)

Description

Given a tree with N vertices and N−1 edges. Each vertex has a single letter Ci. Given a string S, you are to choose two vertices A and B, and make sure the letters catenated on the shortest path from A to B is exactly S. Now, would you mind telling me whether the path exists?

Http

HDU

Tag

点分治,字符串\(Hash\)

题目大意

给出一棵树,每一个点上有一个字符。现在给出一个字符串,求树上是否存在一条路径使得路径上的字符连起来可以得到给出的字符串。

解决思路

考虑点分治强制重心必选,那么就向子树中递归统计答案。为了方便处理字符串匹配,可以采用\(Hash\)的方式,将原字符串正着倒着分别求一遍\(Hash\),得到所有前缀后缀的\(Hash\),那么在点分治的时候,对于递归一棵子树,第一遍先不算重心,与之前的答案尝试组合,分别尝试组合前缀或后缀,第二遍算重心加入信息中以方便后面查询。
为了方便在树上向下递归的时候快速求出当前点到当前根的路径上的字符串的\(hash\)值,这里采用\(BKDRHash\)(是叫这个名字吧?)

代码

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

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

const int maxN=10010;
const int maxM=maxN*2;
const ll Hashbase=19491001;
const int Mod=1000003;
const int inf=2147483647;

int n,nowsum,root,len;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
char Node[maxN],S[maxN];
int Size[maxN],mxSon[maxN];
ll Hashpre[maxN],Hashsuf[maxN];//前缀和后缀分别的hash
bool vis[maxN];
int histcnt=0,Hpre[Mod+10],Hsuf[Mod+10];//histcnt标记当前是第几次,避免memset浪费时间,Hpre和Hsuf分别标记前缀和后缀是否在这一次solve中出现过,方便组合答案
ll Seedret[maxN];
bool is_get_ans;//当得到答案时,退出

void Add_Edge(int u,int v);
void GetRoot(int u,int fa);
void Solve(int u);
void GetAns(int u,int fa,ll nowhash,int depth);
void Modify(int u,int fa,ll nowhash,int depth);

int main()
{
    ios::sync_with_stdio(false);
    int T;cin>>T;
    Seedret[1]=1;
    for (int i=2;i<maxN;i++) Seedret[i]=(ll)Seedret[i-1]*Hashbase%Mod;
    for (int tt=1;tt<=T;tt++)
    {
        edgecnt=0;mem(Head,-1);mem(vis,0);is_get_ans=0;
        cin>>n;
        for (int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            Add_Edge(u,v);Add_Edge(v,u);
        }
        cin>>(Node+1);cin>>(S+1);
        len=strlen(S+1);
        Hashpre[0]=0;//得到hash值
        for (int i=1;i<=len;i++)
            Hashpre[i]=((ll)Hashpre[i-1]*Hashbase+S[i])%Mod;
        Hashsuf[len+1]=0;
        for (int i=len;i>=1;i--)
            Hashsuf[i]=((ll)Hashsuf[i+1]*Hashbase+S[i])%Mod;
        root=0;mxSon[0]=inf;nowsum=n;
        GetRoot(1,0);
        Solve(root);
        printf("Case #%d: ",tt);
        if (is_get_ans) printf("Find\n");
        else printf("Impossible\n");
    }
    return 0;
}

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

void GetRoot(int u,int fa)//得到重心
{
    Size[u]=1;mxSon[u]=0;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((vis[V[i]]==0)&&(V[i]!=fa))
        {
            GetRoot(V[i],u);Size[u]+=Size[V[i]];
            mxSon[u]=max(mxSon[u],Size[V[i]]);
        }
    mxSon[u]=max(mxSon[u],nowsum-Size[u]);
    if (mxSon[u]<mxSon[root]) root=u;
    return;
}

void Solve(int u)//点分治求解
{
    vis[u]=1;
    histcnt++;
    if (Node[u]==S[1]) Hpre[1]=histcnt;//先把重心加入
    if (Node[u]==S[len]) Hsuf[len]=histcnt;
    if (((Node[u]==S[1])||(Node[u]==S[len]))&&(len==1)) is_get_ans=1;//特判字符串长度为1的情况
    for (int i=Head[u];(i!=-1)&&(is_get_ans==0);i=Next[i])
        if (vis[V[i]]==0)
        {
            GetAns(V[i],u,Node[V[i]],1);//先用前面的信息取组合,这时不能算重心
            Modify(V[i],u,((ll)Node[V[i]]*Hashbase%Mod+Node[u])%Mod,2);//再把这一次的加入信息中,以便后面查询,这时就要算重心
        }
    for (int i=Head[u];(i!=-1)&&(is_get_ans==0);i=Next[i])
        if (vis[V[i]]==0)
        {
            root=0;nowsum=Size[V[i]];
            GetRoot(V[i],0);
            Solve(root);
        }
    return;
}

void GetAns(int u,int fa,ll nowhash,int depth)//nowhash记录当前到重心(不包括重心)的字符串hash值
{
    if ((nowhash==Hashpre[depth])&&(Hsuf[depth+1]==histcnt))//组合答案
    {
        is_get_ans=1;
        return;
    }
    if ((nowhash==Hashsuf[len-depth+1])&&(Hpre[len-depth]==histcnt))//组合答案
    {
        is_get_ans=1;
        return;
    }
    for (int i=Head[u];(i!=-1)&&(is_get_ans==0);i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
            GetAns(V[i],u,(Seedret[depth+1]*Node[V[i]]%Mod+nowhash)%Mod,depth+1);
    return;
}

void Modify(int u,int fa,ll nowhash,int depth)
{
    if (nowhash==Hashpre[depth])//当是一个合法前缀或后缀时,更新信息
        Hpre[depth]=histcnt;
    if (nowhash==Hashsuf[len-depth+1])
        Hsuf[len-depth+1]=histcnt;
    for (int i=Head[u];i!=-1;i=Next[i])
        if ((V[i]!=fa)&&(vis[V[i]]==0))
            Modify(V[i],u,(Seedret[depth+1]*Node[V[i]]%Mod+nowhash)%Mod,depth+1);
    return;
}

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

本文链接地址:[HDU5469]Antonidas(点分治,字符串Hash)


HNCJ OIer