Problem #3254 - ECNU Online Judge

单点时限: 3.0 sec

内存限制: 256 MB

起初你想了 $N$ 个长度均为 $k$ 的、由英文小写字母组成的密码 $a_{1}, a_{2}, \dots, a_{N}$ ，为了避免自己忘记，你把它们藏起来：你创造了 $s_{1}, s_{2}, \dots, s_{N}$ 个 $N$ 个字符串，使得 $a_{i}$ 是 $s_{i}$ 的子串。

为了避免自己看到 $s_{i}$ 的时候也想不起自己设的密码，你把 $a_{1}, a_{2}, \dots, a_{N}$ 按顺序藏在了字符串 $T$ 中。也就是说 $T$ 是 $c_{1} a_{1} c_{2} a_{2} \dots c_{N} a_{N} c_{N + 1}$ ，其中 $c_{i}$ $(1 \leq i \leq N + 1)$ 可以是空串。

但是不幸的是，你最终还是忘记了自己设置的密码。现在有 $s_{1}, s_{2}, \dots, s_{N}$ 和 $T$ ，你想知道密码长度最大有可能是多少，即 $k$ 的最大值。

输入格式

输入包含多个测试文件，每个测试文件包含单组测试数据。

第一行是字符串 $T$ 。

第二行是一个整数 $N$ $(1 \leq N \leq 10)$ 。

第 $3$ 至 $N + 2$ 行，每行一个字符串，分别表示 $s_{1}, s_{2}, \dots, s_{N}$ 。

字符串由小写字母组成。

数据约定：

对于 30% 的数据，满足： $l e n (T) \leq 100, \sum_{i} l e n (s_{i}) \leq 500$ 。
对于 60% 的数据，满足： $l e n (T) \leq 20 000, \sum_{i} l e n (s_{i}) \leq 20 000$ 。
对于 100% 的数据，满足： $1 \leq l e n (T) \leq 250 000, \sum_{i} l e n (s_{i}) \leq 250 000$ 。

输出格式

一行一个整数，输出 $k$ 的最大值。

如果无解，输出 $- 1$ 。

样例

Input

abcxzwwwyzxxyzzz
3
yzabcabc
ppwwwwwwwpp
wxxypp

Output

Input

xxxxxxxxxx
3
a
b
c

Output

-1

Input

tttttt
1
ttttttt

Output

提示

样例 1： $a_{1}, a_{2}, a_{3}$ 依次为 abc, www, xxy。

6 人解决，26 人已尝试。

14 份提交通过，共有 169 份提交。

8.6 EMB 奖励。

创建: 7 年，10 月前.

修改: 7 年，7 月前.

最后提交: 2 周，2 天前.

来源: 2017 华东师范大学校赛

string

3254. 忘记密码

输入格式

输出格式

样例

提示

服务

开源

关于我们