4 人解决,14 人已尝试。
4 份提交通过,共有 100 份提交。
8.9 EMB 奖励。
单点时限: 1.0 sec
内存限制: 256 MB
在提瓦特大陆上,每一种魔物都有着对应的字符串 s
。s
是长度不超过 $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$。
输出拥有最大弱化效率的药剂的弱化值和编号。
abcab 2 a c
2 2
cxd 2 a b
1 1
t=a
拼接后的字符串abcaba
可以分为 $1$ 组,相等子串为abcaba
。t=c
拼接后的字符串abcabc
可以分为 $2$ 组,相等子串为abc
。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