Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
Tree-String Problem 【CodeForces - 291E】【倍增(LCA)+哈希】
题目链接 题意 给你N个点的树 树上的边的权值是一个自上往下的字符串 然后我们再给出一个字符串 是模式串 我们现在想知道模式串在树上的出现次数 譬如说样例 我们查找的是aba 它在1 4这条链上出现了2次 在1 5上出现1次 在2 3上出现
LCA算法
哈希
倍增
O(n)RMQ四毛子
有一种ST表 叫做 1ST表 这种ST表可以在 O n O n O n 的时刻内完成建树 其本质就是分块 大块为整除的ST表 小块的差分数组种类不多 完全可以预处理 现在考虑推广到普通的ST表里 我们发现我们真正关心的是数之间的大小关系 但
RMQ
ST表
笛卡尔树
倍增
欧拉环游序