5716：带可选字符的多字符串匹配

题目描述

有一个文本串，它的长度为$m (1 \leq m \leq 2000000)$，现在想找出其中所有的符合特定模式的子串位置。

符合特定模式是指，该子串的长度为$n (1 \leq n \leq 500)$，并且第$i$个字符需要在给定的字符集合$S_{i}$中。

因此，描述这一特定模式，共需要$S_{1},S_{2},...,S_{n}$这$n$个字符集合。每个集合的大小都在$1\sim 62$之间，其中的字符只为数字或大小写字母。

输入解释

第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。

第二行为一个整数$n$。

以下$n$行，分别描述$n$个字符集合。每行开始是一个$1\sim 62$之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。<b>（注：本题有多组测试数据）</b>

输出解释

每当从某个位置开头的，长度为$n$的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从$1$开始。

如果文本串没有任何位置符合输入模式，则最后输出一个字符串"NULL"，占一行。

输入样例

aaaabacabcabd
3
3 abc
2 bc
3 abc

输出样例

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2016"百度之星" - 复赛（Astar Round3）

源链接： HDU-5716

最后修改于 2020-10-25T23:25:03+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	65536/65536K(Java/Others)