Dãy xâu

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho một dãy gồm \(n\) xâu \(s_1,s_2,…, s_n\) và một số nguyên dương \(k\). Một cặp hai xâu \(s_i\) và \(s_j\) trong dãy được gọi là tương thích với nhau nếu thỏa mãn:

  • \(0 < j-i \le k\)
  • Hai xâu \(s_i\) và \(s_j\) có cùng độ dài.

Yêu cầu: Hãy xác định số cặp các xâu tương thích với nhau trong dãy các xâu đã cho.

Input

  • Dòng đầu chứa hai số nguyên \(n\) và \(k\) (\(3 \leq n \leq 3 \times 10^5; 1 \leq k \leq n\)).
  • \(n\) dòng tiếp theo mỗi dòng chứa một xâu có độ dài từ 2 đến 20 kí tự gồm các chữ cái tiếng Anh in hoa.

Output

  • Một dòng duy nhất là kết quả của bài toán.

Scoring

  • Subtask #1 (\(40\%\) số điểm): \(n\leq 5000\)
  • Subtask #2 (\(60\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input 
4 2
OTN
ABC
THA
HUN
Output 
5

Test 2

Input 
6 3
CFETHIA   
LLOYD
STEVIE
KEVIN
MALCABC
DABNEY
Output 
2

Nguồn: 2019 CBH-H.Nam

Bình luận


  • 3
    SPyofgame    1:33 p.m. 19 Tháng 6, 2020

    Bài này cũng hay nè. Mình viết editorial sau nhé ^^


    • 0
      ekhoavvdd    12:30 a.m. 12 Tháng 5, 2021

      đã được 11 tháng :))


    • 0
      tuanha2    8:58 p.m. 6 Tháng 3, 2021

      Đã đc 9 tháng


      • 5
        Hikarii    6:01 p.m. 7 Tháng 3, 2021 ← đã chỉnh sửa
        • Nhận xét: các xâu kia là gì không quan trọng, quan trọng là cái độ dài, nên mình gọi a[i] = độ dài xâu thứ i
        • Tại vị trí thứ i, đếm xem từ (i - k) đến (i - 1) có bao nhiêu phần tử bằng a[i], cộng số này vào đáp án

      • 2
        N7hoatt    12:17 p.m. 23 Tháng 7, 2020

        viết đi a

        3 bình luận nữa