Bàn phím hỏng

Điểm: 3,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một xâu $s$ gồm $n$ ký tự chữ cái Latinh in thường. Bạn có một bàn phím bị hỏng — chỉ còn $k$ ký tự còn hoạt động: $c_{1}, c_{2}, \dots, c_{k}$ .

Hãy đếm số xâu con (đoạn liên tiếp) $s [a \dots b]$ với $1 \leq a \leq b \leq n$ sao cho mọi ký tự trong đoạn đều thuộc tập $k$ ký tự còn hoạt động.

Hai xâu con được xem là khác nhau nếu vị trí $(a, b)$ khác nhau, kể cả khi nội dung trùng nhau.

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các chữ cái Latinh in thường.
Dòng thứ ba chứa $k$ ký tự phân biệt $c_{1}, c_{2}, \dots, c_{k}$ cách nhau bởi dấu cách.

In ra một số nguyên duy nhất — số xâu con của $s$ có thể gõ được chỉ bằng các ký tự còn hoạt động.

Input	Output	Giải thích
7 2 abacaba a b	12	Có thể gõ được các xâu con tại vị trí $[1, 2], [2, 3], [1, 3], [1, 1], [2, 2], [3, 3], [5, 6], [6, 7], [5, 7], [5, 5], [6, 6], [7, 7]$ — tổng 12.
10 3 sadfaasdda f a d	21	Toàn bộ xâu gồm các ký tự thuộc ${a, d, f, s}$ nhưng $s$ không có trong bàn phím nên các đoạn bị chia bởi $s$ .
7 1 aaaaaaa b	0	Không có ký tự $a$ nào gõ được nên không có xâu con hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.