5110. 药剂应对法

单点时限: 1.0 sec

内存限制: 256 MB

在提瓦特大陆上,每一种魔物都有着对应的字符串 ss 是长度不超过 $10^6$ 的字符串且仅包含小写字母。为了最大限度地弱化每种魔物,每位贤者都会挖空心思制作各种药剂。每种药剂对应着字符串 $t$,其中 $t$ 是长度不超过 $10^6$ 的字符串且仅包含小写字母。在将 $s$ 和 $t$ 拼接后,对新的字符串我们可以对其进行分割。一个合法的分割应当将字符串分成多组相同的字符串。在不同的分割方式中,可行的最大分组数即是该药剂的弱化值。

现在给定一个魔物字符串 $s$ 和 $m$ 种药剂的字符串 $t$,请你找出所有药剂中拥有最大弱化值的药剂并输出其弱化值及编号。若有多个相同弱化值的药剂则输出编号较小的药剂。

输入格式

第一行,一个字符串 $s(1\leq |s| \leq 10^6)$,仅包括小写字母。

第二行,一个正整数 $m(1\leq m\leq 10^6)$,表示药剂个数。

接下来 $m$ 行,第 $i$ 行输入一个编号为 $i$ 的药剂字符串 $t_i(1\leq |t_i|\leq 10^6)$。

对于所有的药剂字符串,有 $\sum t_i \leq 10^6$。

输出格式

输出拥有最大弱化效率的药剂的弱化值和编号。

样例

Input
abcab
2
a
c
Output
2 2
Input
cxd
2
a
b
Output
1 1

提示

  • 样例1:
    t=a拼接后的字符串abcaba可以分为 $1$ 组,相等子串为abcaba
    t=c拼接后的字符串abcabc可以分为 $2$ 组,相等子串为abc
  • 样例2:
    t=a拼接后的字符串cxda可以分为 $1$ 组,相等子串为cxda
    t=b拼接后的字符串cxdb可以分为 $1$ 组,相等子串为cxdb

4 人解决,14 人已尝试。

4 份提交通过,共有 100 份提交。

8.9 EMB 奖励。

创建: 1 年,4 月前.

修改: 1 年,4 月前.

最后提交: 7 月,3 周前.

来源: N/A

题目标签