송신기

시간 제한3초메모리 제한1536 MB

요약

연속된 문자열 구간 가운데 모든 쌍의 최장 공통 접두사 길이를 합한 값이 K 이상인 구간의 개수를 구합니다.

난이도: 어려움10점 중 9점
유형: 문자열 매칭, 투 포인터, 유니온 파인드, 문자열
정답자: 아직 제출이 없습니다

문제

Cimrman 연구소 본관은 층마다 라디오 송신기가 한 대씩 있다. 송신기들은 달 뒷면에 있는 Cimrman 달 기지와 통신해야 한다. Cimrman은 강한 신호를 원하므로, 좋은 연결을 얻기 위해 여러 송신기를 동시에 작동시킨다.

다른 실용적인 이유로, 작동하는 송신기는 연속된 층 하나의 블록을 이뤄야 한다. 작동하는 두 송신기 사이에 작동하지 않는 송신기가 끼어 있으면 안 된다.

전송이 시작된 직후, 매초 시작할 때마다 모든 송신기는 조정 주파수로 조정 신호(CoSi)를 보낸다. 송신기마다 고유한 주파수 수열이 있다. $i$ 초의 시작 시점에 송신기는 수열의 $i$ 번째 주파수로 CoSi를 보낸다. CoSi를 보내는 기간은 수열의 길이와 같다. 수열을 다 쓰면 송신기는 CoSi 전송을 멈추지만, 주 작업은 계속한다.

두 송신기로 이루어진 쌍의 성능 품질은, 전송이 시작된 직후부터 두 송신기가 같은 주파수로 CoSi를 보내는 구간의 최대 길이(초)이다. 두 송신기가 서로 다른 주파수로 CoSi를 보내거나, 둘 중 하나가 CoSi 전송을 멈추면 이 구간이 끝난다.

송신기가 세 대 이상인 그룹의 성능 품질은, 그룹 안의 모든 쌍의 성능 품질을 더한 값이다.

성능 품질이 $K$ 이상인, 연속된 층에 있는 송신기 그룹의 개수를 구하라.

입력

첫 줄에 두 정수 $N$ , $K$ 가 주어진다 ( $1 \le N \le 10^6$ , $1 \le K \le 10^9$ ). 다음 $N$ 개의 줄에는 각각 소문자로 된 문자열이 하나씩 주어진다. $i$ 번째 문자열은 $i$ 층 송신기의 CoSi 주파수 수열이며, 문자 하나가 1초에 쓰는 주파수 하나를 뜻한다. 같은 문자는 같은 주파수를, 다른 문자는 다른 주파수를 나타낸다. 모든 문자열 길이의 합은 $10^6$ 이하이다.

출력

성능 품질이 $K$ 이상인 조건을 만족하는 그룹의 개수를 출력한다.

예제2

예제 1
입력
```
4 3
set
stop
setting
state
```
예상 출력
```
3
```
예제 2
입력
```
5 6
a
rating
rating
b
c
```
예상 출력
```
6
```