최근 대회(SUAPC)에서 SA, LCP를 몰라서 2등 했다.
그래서 Suffix Array와 Longest Common Prefix를 공부하였다.
삼소멤의 Suffix Array and LCP Array 글을 보며 공부했다.
공부하다가 알았는데 gumgood님 글이더라 ㄷ! 뭔가 반가웠다 ㅋㅋ
suffix array를 구해보자.
suffix array와 lcp를 구해보자.
KMP기본문제로 유명한 문제인데, 어디선가 SA로 풀 수 있다고 해서 SA로 풀어보았다.
문자열 S에 문자열 T가 몇 번 나타나는지, 그 위치는 어디인지 찾으면 된다.
부분문자열은 접미사의 접두사임을 생각하면 풀이를 떠올릴 수 있다.
SA에 접미사가 정렬된 채로 있으므로 이분탐색을 통해 어떤 문자열의 SA에서의 lower_bound와 upper_bound를 찾으면 그 사이에 있는 개수만큼 문자열이 존재한다. 또한 그 시작 위치는 SA배열의 값이므로 쉽게 알 수 있다.
SA만드는 데에 O(SlogS), 이분탐색에 O(logS), 탐색 때마다 비교하는 데에 O(T)니까 O(S+T)인 KMP보다 느린 O((T+S)logS)에 해결이 가능하다.
가장 긴 반복 부분문자열의 길이를 출력하면 된다. (반복되는 부분문자열끼리 겹쳐도 된다. 즉, aaaaa의 답은 4이다. aaaa)
어떤 두 부분문자열이 동일하다면 각 문자열을 접두사로 하는 접미사는 SA상에서 붙어 있을 것이다. SA는 사전 순으로 되어 있기 때문에 당연하다고 볼 수 있다.
우리는 SA상에서 인접한 두 문자열의 Longest Common Prefix를 LCP배열에 저장해 두었다.
즉, LCP값 중 가장 큰 값이 답이 됨을 알 수 있다.
'LCP의 최댓값 = 가장 긴 반복 부분 문자열의 길이'임을 알 수 있다.
S의 부분문자열 == T의 부분문자열 인 것들 중 가장 길이가 긴 것을 찾으면 된다. 예제를 보면 문제이해가 바로 될 것이다.
INPUT
yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother
OUTPUT
27
howmuchiloveyoumydearmother
처음엔 두 개의 SA를 만들어야 하나 뭐 그런 생각을 했다.
그러다가 위의 1605 반복 부분문자열 문제와 굉장히 비슷하다는 것을 느꼈다.
사실상 두 문자열을 이어 붙이면 1605와 똑같은 문제가 되는 걸 알 수 있다.
그런데 그냥 이어 붙이면 두 문자열에 걸치는 문자열도 부분문자열로 생각할 수 있다.
이는 사이에 이상한 더미 문자를 하나 끼워 넣어 해결할 수 있다.
즉, s+'$'+t 문자열에서의 최대 LCP 값을 찾으면 된다.
해결을 잘 한 줄 알았는데, WA를 받았다. 이유는 두 문자열을 붙였는데, 가장 긴 반복 부분 문자열이 모두 한 문자열에서 나오는 경우였다.
따라서 SA값을 비교해서 서로 다른 문자열의 부분문자열인 경우에만 답이 될 수 있다. 이 부분을 잘 처리하면 AC를 받을 수 있다.
S에서 서로 다른 부분 문자열의 개수를 출력해야 한다.
부분 문자열은 접미사의 접두사이니까... 같은 부분 문자열은 SA상에서 인접할 수밖에 없다. 그러면 LCP의 크기만큼 전체 경우에서 빼주면 된다.
S에서 사전 순으로 K번째인 부분문자열을 출력해야 한다.
SA를 만들면 접미사들이 사전 순으로 배치된다. 부분 문자열은 접미사의 접두사이다.
그렇다면 각 Suffix에서 나올 수 있는 부분문자열의 개수를 구해보자. 이때, SA상에서 바로 앞 접미사와 겹치는 부분만큼은 빼주어야 한다.
즉, cnt[i]=(S의 길이)-SA[i]-LCP[i]이다.
이제 cnt[i]에 대한 누적합을 만들자.
그 후, 쿼리마다 이분탐색을 통해 k번째 문자열을 찾을 수 있다.
최소 m번 등장하는 부분 문자열의 최대 길이를 출력해야 한다.
그리고 그 부분 문자열 중 가장 오른쪽에 있는 것의 시작 인덱스를 출력해야 한다.
길이가 x인 부분문자열이 m번 등장한다면, 길이가 x-1, x-2, ...인 부분문자열은 당연히 m번 이상 등장한다.
parametric이 떠오른다.
이제 m번 등장하는 길이가 k인 부분문자열이 있는지 생각해보자.
같은 부분문자열은 SA상에서 인접하다. 즉, m개가 연속으로 있으면 똑같은 부분문자열은 m개가 있다는 것이다. 여기에 LCP값이 모두 k 상이라면 그 부분문자열 m개의 길이는 최소 k임을 알 수 있다.
이는 LCP를 통해 찾을 수 있다. 연속된 m-1개의 lcp 값이 모두 k이상이면 m번 등장하는 길이가 k인 부분문자열이 있는 것임을 쉽게 알 수 있다.
문자열 T가 주어지면 T의 부분문자열 S의 최대 점수를 구하는 문제이다.
최대 점수는 (S의 길이)*(T에서 S가 등장하는 횟수)이다.
부분문자열은 접미사의 접두사이다...ㅋㅋ!
SA배열에서 여러 번 등장하는 부분문자열들이 포함된 접미사들은 서로 이웃하여 있다.
즉, LCP 배열 상에서 (어떤 구간의 길이+1) * (구간 내 LCP의 최솟값)의 최댓값을 구하면 된다.
어떻게 구현할까 계속 고민하다가 직접 값 몇 개를 써보니까 히스토그램이랑 똑같은 걸 깨달았따. 이게 왜 바로 안보였을까 싶다.... 멍청한 듯
LCP코드에 히스토그램 코드 복붙해서 냈는데 WA 떴다.
모든 부분 문자열이 다 한 번씩만 나올 때를 처리를 못했다. 이럴 땐 답이 그냥 (문자열의 길이)이다.
이 문제가 SA와 LCP를 공부한 이유였다. 이번 SUAPC에서 우리 팀이 풀지 못한 문제였다.
부분 문자열 중 영우 문자열인 것의 개수를 세자.
영우 문자열이란 K이상인 팰린드롬을 부분 문자열로 가지는 문자열이다.
어떤 접미사를 S라하자. S내에서 K이상인 팰린드롬이 처음으로 나타나는 위치를 저장해 주자. S의 접두사 중에서 끝나는 곳이 K이상인 팰린드롬 뒤쪽인 문자열들은 모두 영우 문자열이다...
그리고 LCP를 통해서 겹치는 부분문자열을 잘 처리하면 되는 문제이다.
조금... 뭐랄까 구현이 까다롭고 귀찮은 문제였다. (내가 못한걸 수도)
매내처를 알고 있고, 위에 있는 문제들을 잘 풀었다면 충분히 풀 수 있는 문제라고 생각한다.
그냥 배운 거 연습하기 꽤 괜찮은 문제인 것 같다.
자세한 풀이는 https://archive.suapc.kr/2022s/solution/ 에서 확인하자.
기본문제들 위주로 풀어봤는데, 주로 부분문자열이 접미사의 접두사임을 이용하여 문제를 해결하는 것 같다.
'PS > 알고리즘' 카테고리의 다른 글
| 순열 사이클 분할의 성질 (6) | 2023.01.07 |
|---|---|
| [백준] 열혈강호 시리즈 (C++) (4) | 2022.02.08 |