本文共 1992 字，大约阅读时间需要 6 分钟。

题目来源：

Description

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.

Input

The first line contains two space-separated integers n and k (1≤n≤2⋅105, 1≤k≤26) — the length of the string s and the number of Latin letters still available on the keyboard.

The second line contains the string s consisting of exactly n lowercase Latin letters.

The third line contains k space-separated distinct lowercase Latin letters c1,c2,…,ck — the letters still available on the keyboard.

Output

Print a single number — the number of substrings of s that can be typed using only available letters c1,c2,…,ck.

Sample Input

7 2

Sample Output

12

AC代码：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'bool arr[26];using ll = long long;int main(){
       SIS;    char ch;    int n,k;    cin >> n >> k;    string s;    cin >> s;    for(int i=0;i
    
     > ch;        arr[ch-'a']=true;    }    ll ans=0,cnt=0;    for(int i=0;i
    
   

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'using ll = long long;int main(){
       SIS;    int n,k,cnt=0;    cin >> n >> k;    string s;    char ch;    cin >> s;    map
    
      m;    for(int i=0;i
     
      > ch;        m[ch-'a']=true;    }    vector
      
        v;    for(int i=0;i
      
     
    
   

转载地址：http://lsyof.baihongyu.com/