题意:
对于26个字母 每个字母分别有一个权值
给出一个字符串,找出有多少个满足条件的子串,
条件:1、第一个字母和最后一个相同,2、除了第一个和最后一个字母外,其他的权和为0
思路:
预处理出sum[i]:s[0~i]的和
开26个map<LL, LL>numV 分别表示 每个字母前缀和 的个数
例如处理到第i个元素,且numV[s[i]-'a'][sum[i]-v[s[i] - 'a']] (值为2)
表示在处理到的元素之前 以s[i]结尾的前缀和为sum[i]-v[s[i]-'a']的个数有2个
所以答案就要加2(因为前面已经组成过这个值,又出现的原因就是他的值变为了0)
const int maxv = ;
int v[maxv];
map<LL, LL> numV[maxv]; const int maxn = + ;
char s[maxn];
LL sum[maxn];
void init()
{
for (int i = ; i < ; i++)
{
scanf("%d", v + i);
}
scanf(" ");
gets(s);
} void solve()
{
int len = strlen(s);
sum[] = v[s[]-'a'];
for (int i = ; i < len; i++)
{
sum[i] = sum[i-] + v[s[i]-'a'];
} LL ans = ;
for (int i = ; i < len; i++)
{
ans += numV[s[i]-'a'][sum[i] - v[s[i] - 'a']];
numV[s[i]-'a'][sum[i]]++;
}
printf("%lld\n", ans);
} int main()
{
init();
solve();
return ;
}