Dãy xâu

Xem PDF

Đ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\)\(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\)\(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\)\(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


  • 0
    hien18086 6:19 p.m. 22 Tháng 2, 2024

    • 0
      gkthcsyl 4:44 p.m. 21 Tháng 7, 2023

      include<bits/stdc++.h>

      using namespace std;
      long long i,n,d;
      string s;
      int main (){
      d=0;
      cin>>s;
      if(s[0]=='-')
      s.erase(0,1);
      while(s!=""){
      s.erase(0,1);
      d++;
      }
      cout<<d;
      return 0;
      }


      • 0
        VoBaThongL921 10:42 a.m. 28 Tháng 11, 2021

        Đếm phân phối + sliding window


        • 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é ^^

          3 phản hồi