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

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


本文章由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\)(是叫这个名字吧?)

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

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


HNCJ OIer 一枚