코딩스토리

백준 9248번 - Suffix Array www.acmicpc.net/problem/9248 9248번: Suffix Array Suffix Array란, 문자열 S가 있을 때 그 접미사들을 정렬해 놓은 배열이다. 예를 들어, 문자열 S=banana의 접미사는 아래와 같이 총 6개가 있다. Suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 이를 Suffix 순으로 정 www.acmicpc.net 이 문제는 접미사 배열 문제이다. 오전에 맨버 마이어스 알고리즘을 공부해서 쉽게 풀 수 있을 것 같아서 풀어보았다. 테스트 케이스도 다 정확히 나오길래 드디어 플래 문제를 풀어보는구나 했는데 시간 초과.. 도저히 어디가 문젠 지도 모르겠고.. 구글링은 귀찮고.. 뭔가 이상해서..

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 이전에 KMP알고리즘에 대해 알아 보았었다.그럼에도 문자열 문제는 쉽지 않다. 가장 최근 2020 카카오 코딩 테스트를 보면 문자열 문제가 시작부터 연달아 나옴을 알 수 있다. 그만큼 중요하면서도 어려운 유형이다. 이번에는 접미사를 통해 문자열 알고리즘을 좀 더 확장시켜 보려고 한다. 1. 접미사 배열 문자열을 다룰 때 빼놓을 수 없는 자료구조로 접미사 배열이 있다고 한다. '문자열의 맥가이버 칼' 이라고도 부른다는데 한번 공부해 보도록 하자. 먼저 접미사 배열은 말 그대로 한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것을 말한다. 이때 접미사들을 그대로 저장하면 문자열의 길이..