← 返回题目列表

AtCoder · jsc2019_final_e

E. 最近的字符串

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

配点 : 800 点

問題文

高桥君是一个字符串 对于 a ,以下内容 可以执行 2 类型的操作。 在

  • a 的开头或结尾 1 删除字符。这包括 它的成本是 X 会产生成本。
  • a 末尾, 1 添加字符。这包括 Y 会产生成本。

高桥君现在是N 字符串 S_0,S_1,\cdots,S_{N-1} 。 高桥君的朋友青木君告诉高桥君以下的事情。 问 Q 问题。

  • 質問 i (0 \leq i \leq Q-1): 青木君是一个字符串 显示 T_i 。 对 T_i 重复上述操作,看看高桥有什么。 找出匹配任何 N 字符串所需的最低成本。

高桥君,请在百忙之中编写一个程序来回答这些问题。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq X,Y \leq 10^9
  • 1 \leq |S_i|
  • \sum_{i=0}^{N-1} |S_i| \leq 5 \times 10^5
  • S_i \neq S_j (i \neq j)
  • 1 \leq |T_i|
  • \sum_{i=0}^{Q-1} |T_i| \leq 5 \times 10^5
  • T_i \neq T_j (i \neq j)
  • 输入的所有数字均为整数。
  • 所有输入字符串均由小写英文字母组成。

入力

输入是按以下格式从标准输入给出的。

N Q X Y
S_0
S_1
\vdots
S_{N-1}
T_0
T_1
\vdots
T_{Q-1}

出力

Q 行。 i+1 (0 \leq i \leq Q-1) 行包含问题 i 的答案。 对于第


入力例 1

3 3 4 2
b
bcd
cd
a
ab
abc

出力例 1

6
4
6

例如,问题 考虑到 2 ,最好的操作方法如下。 删除

  • abc 的第一个字符并 获取bc 。成本是 4 需要。
  • bc 结束时 输出为 d 和bcd 。成本是 2 需要。

入力例 2

4 3 1 100
a
aaaa
aaaaaaa
aaaaaaaaaa
aaa
aaaaaa
aaaaaaaaa

出力例 2

2
2
2

入力例 3

10 10 86 69
bbabbaaaaa
babaababab
bbababbbba
aaaaaaaaab
bbbbbbaabb
aabbabbbba
babbbbbbaa
baaabbaaaa
aaaaababbb
ababaaaaaa
bbaabbbbaa
abbbbabbbb
abbaaabaaa
ababaaaaab
bbaabbaaaa
abbbbbbabb
aabbbabbba
aaabbbaaaa
abbbababab
babaaabbbb

出力例 3

930
620
775
155
775
465
775
930
620
620