목록전체 글 (41)
N coding
3789_Hidden password
https://www.acmicpc.net/problem/3789 suffix array nlog n으로 짠 코드plzrun님 블로그에서 많이 참고하고 마리오블로그에서 lcp부분만 참고했다. 어떤 password가 주어졌을때그걸 왼쪽으로 1번씩 민 각각의 문자열 중에 가장 사전순으로 작은 아이의 시작 인덱스를 출력하면 된다. alabla 를 한번씩 민다면lablaaablaalblaala ... 이런식으로 총 n개가 나올 것이다이것들을 사전 순으로 정렬했을때 가장 위에 오는 문자열의 맨 처음 문자가 원래 문자열의 몇번째 애인지 출력하는 거임. 결국에는 환형이 되므로 나는 입력받은 문자열을 붙여서 2배로 늘리고가장 먼저 나오는 n보다 작은 인덱스를 출력하는데,문자열이 사전 순으로 같은 경우 인덱스가 작은 걸..
PS
2018. 8. 29. 15:49