COCI 2012/2013 contest 3 task 3 Malcolm- 강줄기2 > 문제은행 : 정보올림피아드&알고리즘




1796 : 강줄기2

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
15 회   
시도횟수
60 회   

문제

훌륭한 자연경관을 가지고 있어서 관광객이 많이 오는 A산에 강이 흐르는데, 강줄기를 따라 직선으로 N개의 시설이 있다. 

각각의 시설들은 각자 이름이 하나씩 있다.


A산에 여행하러 온 지헌이는 강줄기를 따라 래프팅을 할 것이다. 

지헌이는 래프팅 코스를 정해야 하는데, 래프팅 코스의 길이는 R 이하여야 하고 래프팅 코스의 시작점과 끝점에 있는 두 시설의 이름의 길이가 같아야 한다. 

당연히 래프팅 코스는 상류에서 하류 쪽으로 가야 한다.


지헌이는 자신의 조건을 만족시키는 래프팅 코스가 얼마나 많은지 알아보려고 한다. 지헌이를 만족시키는 래프팅 코스의 수를 구해보자.


입력형식

첫 번째 줄에는 N (3 ≤ N ≤ 300,000)과 R (1 ≤ R ≤ N) 이 주어진다.
두 번째 줄부터 N개의 줄에는 상류에서 하류까지 가면서 나오는 시설들의 이름이 주어진다. 시설의 이름은 2~20개의 알파벳 대문자로 이루어져 있다.


출력형식

지헌이를 만족시키는 래프팅 코스의 수를 출력한다.


입력 예

5 2
PIZZA
CUTLET
PASTA
BREAD
CHICKEN

출력 예

2

입력 예

6 3
PENSION
CAFE
HOTEL
JAZZ
MUSICAL
PASTA

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP