2018. 4. 30. 23:25, 알고리즘/BOJ
https://www.acmicpc.net/problem/11478
문제의 예시에서 일단 Suffix Array를 만들어놓고 시작하겠습니다.
ababc
abc
babc
bc
c
이 때 빨간색 부분이 윗 문자와의 LCP입니다. 빨간색 부분은 중복되기 때문에 횟수를 세면 안되고, 검은색을 포함하면 중복되지 않기 때문에 각각에 대해서 중복되지 않은 문자열은 아래와 같이 추출이 가능합니다.
ababc -> a / ab / aba / abab / ababc
abc -> abc
babc -> b / ba / bab / babc
bc -> bc
c -> c
즉 LCP의 갯수만큼 횟수가 줄어들게 되니까 len*(len+1)/2 - sum of LCP가 정답이 됩니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 7662번: Dual Priority Queue (0) | 2018.05.03 |
---|---|
[BOJ] 1043번: 거짓말 (0) | 2018.05.02 |
[BOJ] 4781번: Candy Store (0) | 2018.05.01 |
[BOJ] 9248번: Suffix Array (0) | 2018.04.30 |
[BOJ] 11585번: 속타는 저녁 메뉴 (0) | 2018.04.26 |
[BOJ] 9661번: 돌 게임 7 (0) | 2018.04.26 |
Comments