공통 접두사 쌍 세기
골드 I의견: 0
\(N\)개의 문자열이 주어진다. 두 문자열의 최장 공통 접두사(LCP)란 두 문자열의 앞에서부터 연속으로 일치하는 최대 길이를 말한다.
서로 다른 두 문자열의 쌍 \((i, j)\) (\(i < j\)) 중에서, 그 LCP의 길이가 \(K\) 이상인 쌍의 개수를 구하라.
\(1 \le N \le 100{,}000\), \(1 \le K \le 1{,}000{,}000\). 모든 문자열 길이의 합은 \(1{,}000{,}000\) 이하이다. 각 문자열은 영소문자와 숫자로 이루어진다.
첫째 줄에 문자열의 수 \(N\)과 정수 \(K\). 다음 \(N\)개의 줄에 각각 소문자/숫자로 이루어진 문자열이 주어진다 (같은 문자열이 여러 번 나올 수 있다).
조건을 만족하는 쌍의 개수를 한 줄에 출력한다.
5 2
apple
apply
app
banana
band
4길이 \(\ge2\) 접두사 기준: ap가 apple, apply, app 세 개 → \(\binom{3}{2}=3\)쌍. ba가 banana, band 두 개 → \(1\)쌍. 합 \(4\).
4 3
abcde
abcxy
abxyz
zzz
1길이 \(\ge3\) 접두사 abc를 가진 단어는 abcde, abcxy 두 개 → \(1\)쌍. abxyz는 abx로 혼자, zzz도 혼자. 답 \(1\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
공통 접두사 쌍 세기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
공통 접두사 쌍 세기