0824 연습

셋 제작자: imtore

• A - 게임 닉네임
• B - 마법의 문자열
• C - 복붙하기
• D - 가장 긴 공통 부분 문자열
• E - 가장 긴 공통부분 팰린드롬
• F - 적절한 문자열 문제
• G - IQ 테스트
• H - Sequence Conversion 2
• I - 홀수 싸이클

A~F는 문자열 셋이고 G,H,I는 내가 참여하지 않았던 어떤 셋의 imtore님의 업솔빙이다. (이 3문제 빼고 다 업솔빙하셨다고 한다 :god:)

 

A: 트라이 기본. 문자열의 끝을 나타낼 변수를 따로 정해줘야 합니다.

http://boj.kr/2d9a845d3d0a4ab789996d416312ff7f

B: 첫번째 단어는 고정시킬 수 있습니다. (하면 빠릅니다.)
가능한 모든 순열에 대해 이어붙인 문자열을 검사하면 됩니다.

방법1: 문자열을 $s$라 할 때 $s + s$에서 $s$가 $K+1$번 나오는지 판정

http://boj.kr/abcbaae5a6d84a3796034d0654a31c12

방법2: 문자열의 길이를 $l$이라 할 때 $l$의 약수 $d$에 대해 길이 $d$의 접두사를 $l/d$번 곱해 원 문자열을 만들 수 있는 $d$의 최솟값 구하기.

ex( ABABAB면 AB를 3번 곱해 ABABAB를 만들 수 있음)

http://boj.kr/b7d4f7b5f727405497f359fa3288ece8

C: 이분탐색 + 라빈카프로 뚫을 수 있습니다. 길이 M의 부분 문자열이 2번 등장하면 M2 <= M인 M2에 대해서도 성립하기 때문에 이분탐색을 적용할 수 있습니다. 롤링 해시를 구현할 때는 문자열의 앞이 더 높은 자릿수가 되도록 구현하는게 편합니다. 반대로 할 경우 탐색도 거꾸로 하거나 모듈러 인버스를 사용해줘야 하는데 이는 매우 귀찮습니다.
B = 127, M =2e6+7 정도로 해놓고 $ b = B^{len-1} $를 저장해놓습니다. 앞에서부터 차례대로 h = (h*B+s[i]) %M 을 해줘서 초기값을 설정한 다음 같은 방식으로 쉬프트 하면 됩니다.

http://boj.kr/357ae6ea9dfd4bf0ae0dd97912c62a43

D:C와 비슷하게 이분탐색 + 라빈카프로 뚫을 수 있습니다. 다만 C의 경우 라빈카프에서 실제로 문자열을 비교하는 과정을 거쳐주었는데 여기서는 aa...aa/aa...aa/.../aaaa..aab 와 같은 최악의 경우가 있을 수 있기 때문에 Mod를 매우 크게 설정한 다음 map(dict)에 넣어서 문자열 비교과정 없이 바로 판정하는 방법을 이용했습니다. 해싱으로(C++) 이 문제를 푼 사람들 대부분 비슷한 방법으로 set을 이용했습니다. Python은 큰 수 연산이 가능하므로 pypy3 가능 + python 추가시간만 제대로 주어진다면 해싱도 나쁘지 않을 것 같네요.

http://boj.kr/55824c1718c04e1abfbccb31d9c5db65

E: EERTree

F: 논문 문제?

G: 연립방정식 풀면 된다는 추측, 귀찮다

H: 단조 덱 만들면 될거 같은데 확실하지 않다.

I: SCC 만들고 잘 하면 될 것 같다.