공통의 흔적
다이아몬드 II의견: 0
\(N\)명의 탐험가가 각자 자신만의 기록을 남겼다. \(i\)번째 탐험가의 기록은 소문자 알파벳으로만 이루어진 문자열 \(S_i\)이다.
어떤 문자열 \(t\)가 적어도 \(K\)명의 탐험가의 기록 안에 (연속한 부분으로) 등장한다면, \(t\)를 공통의 흔적이라고 부른다. 즉, \(t\)가 \(S_i\)의 연속 부분문자열인 탐험가가 \(K\)명 이상 존재하면 된다.
가장 긴 공통의 흔적의 길이를 구하고, 그 최대 길이를 갖는 서로 다른 공통의 흔적이 몇 개인지 구하여라. 길이가 같더라도 문자열로서 서로 다르면 다른 것으로 센다.
공통의 흔적이 하나도 존재하지 않는 경우(즉 어떤 문자열도 \(K\)명 이상에게 공통이 아닌 경우는 없으나, 빈 문자열은 흔적으로 세지 않으므로 길이 \(0\)이 답이 될 수 있다)에는 길이와 개수를 모두 \(0\)으로 출력한다.
\(1 \le K \le N\)
\(1 \le N \le 100{,}000\)
모든 \(|S_i|\)의 합은 \(150{,}000\) 이하이다.
각 \(S_i\)는 소문자 알파벳('a'~'z')으로만 이루어진다.
첫 줄에 정수 \(N\)과 \(K\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 각 탐험가의 기록 \(S_i\)가 한 줄에 하나씩 주어진다. 각 \(S_i\)는 비어 있지 않은 소문자 알파벳 문자열이다.
한 줄에 두 정수를 공백으로 구분하여 출력한다. 첫 번째 정수는 가장 긴 공통의 흔적의 길이이고, 두 번째 정수는 그 길이를 갖는 서로 다른 공통의 흔적의 개수이다.
4 3
abcabc
zabcz
abce
xxabcd
3 1네 기록 중 "abc"는 첫째·둘째·셋째·넷째 모두에 등장하므로 4명 공통, 길이 3. 길이 3을 넘는 흔적 중 3명 이상 공통인 것은 없다. 따라서 가장 긴 길이는 3이고, 그 길이를 갖는 공통의 흔적은 "abc" 하나뿐이므로 개수는 1이다.
3 2
aa
aab
baa
2 12명 이상에 공통인 가장 긴 흔적을 찾는다. "aa"는 세 기록 모두에, "ba"는 둘째·셋째에, "ab"는 첫째에는 없다. 길이 2짜리로 2명 이상 공통인 것은 "aa"와 "ba" 두 가지이다. 길이 3 이상은 2명 공통이 없다. 따라서 길이 2, 개수 2.
riseoj 작성
출처 Original
평가 및 의견
공통의 흔적
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
공통의 흔적