YZOJ P3897 Sevenk Love Oimaster

YZOJ P3897 Sevenk Love Oimaster

时间限制:1000MS      内存限制:131072KB

难度:\(7.5\)

  • 题目描述

有 \(n\) 个大串和 \(q\) 个询问,每次给出一个字符串 \(s\) 询问在多少个大串中出现过。

  • 输入格式

输入的第一行有两个整数分别代表 \(n\) 和 \(q\) 。

接下来的 \(n\) 行,分别给出题中所述的 n个只包含小写字母的字符串。

再接下来的 \(q\) 行,每行给出一个询问只包含小写字母的字符串。

  • 输出格式

对于每一个询问,输出一行答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(n \leq 10000, q \leq 60000\) 。

原串总长度 \(\leq 100000\) 。

询问串总长度 \(\leq 360000\) 。

 

 

 

Source: BZOJ 2780 && SPOJ 8093


 

 

 

首先因为有多个模式串,所以建立一个广义SAM,并记录每个节点属于哪个串。

每个询问都在广义SAM上跑匹配,询问的答案就是最终匹配到的节点在 parent 树中的子树所包含的不同大串的数量。

显然可以在 parent 树上用 std::set 启发式合并,时间复杂度 \(O(nlog^2n)\) 。

或者按照 DFS序 离线用树状数组解决,时间复杂度 \(O(nlogn)\) 。

 

 

 

 

发表回复

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