← 返回题目列表

Codeforces · 519/D

D. A 和 B 以及有趣的子串

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

A 和 B 正在准备编程竞赛。

经过几年的体育编程和解决许多需要计算各种抽象对象的问题,A和B也形成了相当奇特的品味。

A 喜欢拉丁字母中的小写字母。他为每个字母分配了一个数字,表明他有多喜欢该字母(他为他不喜欢的字母分配了负数)。

B 喜欢子串。他特别喜欢那些以相同字母开头和结尾的字母(它们的长度必须超过一个)。

另外,A 和 B 有一个字符串 s。现在他们试图找出字符串s中有多少个子串t是B感兴趣的(即t以相同的字母开头和结尾且长度大于1),以及所有字母(由A指定)的值之和等于0,除了第一个和最后一个。

自然地,A和B很快就找到了他们感兴趣的子串t的数量。你能做到吗?

输入

第一行包含 26 个整数 xa, xb, ..., xz (- 105 ≤ xi ≤ 105) — 分别分配给字母 a, b, c, ..., z 的值。

第二行包含长度在 1 到 105 个字符之间的字符串 s,由后面的小写字母组成 - 您需要计算答案的字符串。

输出

打印问题的答案。

示例

输入 #1

1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
xabcab

输出 #1

2

输入 #2

1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 7 1 1 1 8 1 1 1 1 1 1
aaa

输出 #2

2

注意

在第一个样本中,满足上述条件的测试字符串是 abca 和 bcab。

在满足上述条件的第二个示例测试字符串中出现了两次 aa。