← 返回题目列表

Codeforces · 79/C

C. 海狸

中文机器翻译题面 查看原题

Fox Ciel下车后,发现自己坐错了车,在陌生的小镇迷了路。然而幸运的是,她遇到了她的朋友海狸太郎,并询问去她的城堡走哪条路。太郎给她的回应是字符串s,她尝试着正确地记住字符串s。

然而,Ciel 觉得 n 个字符串 b1, b2, ... , bn 真的很无聊,不幸的是她不喜欢记住一个包含无聊子串的字符串。更糟糕的是,她能记住的只是 s 的连续子串。

确定 s 中不包含任何无聊字符串的最长连续子串,以便她能够记住太郎响应中最长的部分。

输入

第一行有一个字符串 s。 s 的长度将在 1 到 105 之间(包含 1 和 105)。

第二行有一个整数 n (1 ≤ n ≤ 10)。 接下来的 n 行,有一个字符串 bi (1 ≤ i ≤ n)。 bi 的每个长度将在 1 到 10 之间(包含 1 和 10)。

给定字符串的每个字符将是英文字母(小写和大写)或下划线('_')或数字。假设这些字符串区分大小写。

输出

在第一行输出两个空格分隔的整数 len 和 pos:s 中不包含任何 bi 的最长连续子串的长度,以及子串的第一个位置(从 0 开始索引)。位置 pos 必须介于 0 和 |s| 之间- len 包含在内,其中 |s|是字符串 s 的长度。

如果有多个解,则输出任意一个。

示例

输入 #1

Go_straight_along_this_street
5
str
long
tree
biginteger
ellipse

输出 #1

12 4

输入 #2

IhaveNoIdea
9
I
h
a
v
e
N
o
I
d

输出 #2

0 0

输入 #3

unagioisii
2
ioi
unagi

输出 #3

5 5

注意

在第一个示例中,解为 traight_alon。

在第二个示例中,解决方案是空字符串,因此输出可以是“0 0”、“0 1”、“0 2”等。

在第三个示例中,解决方案是 nagio 或 oisii。