시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 96 | 19 | 15 | 24.194% |
길이가 $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$로 가능한 문자열의 개수를 출력한다.
5 3 bridgetown georgetown freetown capetown kingstown
2
5 5 bridgetown georgetown freetown capetown kingstown
10
3 2 aaaaa bbbb ccc
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번