链接:
https://codeforces.com/contest/1272/problem/C
题意:
Recently, Norge found a string s=s1s2…sn consisting of n lowercase Latin letters. As an exercise to improve his typing speed, he decided to type all substrings of the string s. Yes, all n(n+1)2 of them!
A substring of s is a non-empty string x=s[a…b]=sasa+1…sb (1≤a≤b≤n). For example, "auto" and "ton" are substrings of "automaton".
Shortly after the start of the exercise, Norge realized that his keyboard was broken, namely, he could use only k Latin letters c1,c2,…,ck out of 26.
After that, Norge became interested in how many substrings of the string s he could still type using his broken keyboard. Help him to find this number.
思路:
遍历一边计数,一个长为n的串的所有子串是1+2++n。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5;
char s[MAXN];
int main()
{
int n, k;
cin >> n >> k;
cin >> s;
map<char, bool> Mp;
char c;
for (int i = 1;i <= k;i++)
{
cin >> c;
Mp[c] = true;
}
int len = strlen(s);
LL ans = 0, tmp = 0;
for (int i = 0;i < len;i++)
{
if (!Mp[s[i]])
{
ans += (1+tmp)*tmp/2;
tmp = 0;
continue;
}
tmp++;
}
if (tmp > 0)
ans += (1+tmp)*tmp/2;
cout << ans << endl;
return 0;
}