分类： 广义SAM

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…

YZOJ P3939 [HAOI2016]找相同字符

YZOJ P3939 [HAOI2016]找相同字符

时间限制：1000MS      内存限制：262144K

难度：\(6.5\)

  • 题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

两个方案不同当且仅当这两个子串中有一个位置不同。

  • 输入格式

两行，两个字符串 \(s_1, s_2\)，\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\)，字符串中只有小写字母。

  • 输出格式

输出一个整数表示答案

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 4566…

YZOJ P2242 [ZJOI 2015]Substring

YZOJ P2242 [ZJOI 2015]Substring

时间限制：1000MS      内存限制：524288KB

难度：\(8.0\)

  • 题目描述

给出一棵 \(n\) 个节点、叶子不超过 \(20\) 个的树，每个节点上有 \(0\) 到 \(c-1\) 的数字。

树上任意两点 \(A\)、\(B\) 间的有向路径 \(A \rightarrow B\) 形成了一个字符串（\(A \rightarrow B\) 和 \(B \rightarrow A\) 构成的串相反）。

求总共有多少个互不相同的字符串。

  • 输入格式

第一行两个数，\(n, c\) 。

第二行 \(n\) 个 \(0\)~\(c-1\) 间的数，表示每个节点的颜色。

接下来 \(n-1\) 行，每一行表示一条树边。

保证叶子个数不超过 \(20\)。

  • 输出格式

一个整数，表示不同的字符串数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(1 \leq n \leq 10000, 1 \leq c \leq 10\) 。

 

 

 

Source: BZOJ 3926…