[백준 3078] 좋은 친구

 

3078번: 좋은 친구

 

길이가 $K + 1$인 $[l, r]$ 구간을 잡고 슬라이딩 윈도우로 보면서 $[l, r]$ 구간에서 $l$ 번째와 문자열의 길이가 같은 것의 개수를 세주면 된다.

 

import sys

def input():
    return sys.stdin.readline().rstrip()

N, K = map(int, input().split())
S = [input() for i in range(N)]
cnt = [0 for i in range(21)]
ans, r = 0, -1

for i in range(N):
    while r + 1 < N and r + 1 - i <= K: 
        r += 1
        cnt[len(S[r])] += 1

    ans += cnt[len(S[i])] - 1
    cnt[len(S[i])] -= 1

print(ans)