시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 1024 MB298850.000%

문제

길이가 $1$ 이상이고 알파벳 소문자로만 이루어진 미지의 문자열 $X$가 있다.

이 문자열을 알아내기 위해 $N$개의 단서 $S_1$, $S_2$, $\cdots$, $S_N$을 모았다.

$N$개의 단서 중 $X$를 부분문자열(substring)로 가지는 것이 정확히 $K$개 있음을 알게 되었다.

이때 $X$로 가능한 문자열은 몇 개가 있을까?

입력

첫째 줄에 두 정수 $N$과 $K$가 주어진다. ($1 \le N \le 500\,000$, $1 \le K \le N$)

이후 $N$개 줄에 걸쳐 알파벳 소문자로만 이루어진 문자열 $S_i$가 각각 주어진다. ($1 \le |S_i| \le 500\,000$, $|S_1| + |S_2| + \cdots + |S_N| \le 500\,000$)

출력

첫째 줄에 $X$로 가능한 문자열의 개수를 출력한다.

예제 입력 1

5 3
bridgetown
georgetown
freetown
capetown
kingstown

예제 출력 1

2

예제 입력 2

5 5
bridgetown
georgetown
freetown
capetown
kingstown

예제 출력 2

10

예제 입력 3

3 2
aaaaa
bbbb
ccc

예제 출력 3

0

노트

첫 번째 예제에서 $X$로 가능한 문자열은 g, r가 있다.

두 번째 예제에서 $X$로 가능한 문자열은 t, o, w, n, to, ow, wn, tow, own, town이 있다.

문자열 $A$가 문자열 $B$를 부분문자열로 가진다는 것은 $A$의 양 끝에서 각각 $0$개 이상의 문자를 지워 $B$를 만들 수 있음을 의미한다.

출처

University > 서울대학교 > 2021 서울대학교 프로그래밍 경시대회 - Division 1 J번