Daily PS Comments #3

매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다.

완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요.

 

• Suffix array 기본 문제 몇 개랑 상어의 저녁식사 풀었습니다.
• 딱히 어려운 부분은 없었습니다.

 

Prefix와 Suffix

링크

• 일단 해싱으로 pfx=sfx들을 효율적으로 구할 수 있고,
• 이것들이 몇 번 등장하는지를 suffix array를 갖고 구할 수 있지 않을까 하는 생각이 듭니다.
• LCP 배열에서 RMQ를 돌리면..! 어떤 패턴이 몇 번 등장하는지를 손쉽게 확인할 수 있겠다는 신선한 생각이 들었습니다.
• 해보겠습니다..!

 

• 구현량에 걸맞지 않게 한 번에 예제가 나왔습니다.
• 제출했더니 99% OOB가 뜨네요... 어느 부분이징
• |S|=1만 예외처리 해주니까 되네욥