shjgkwo   8년 전

별다른 뾰족한 수가 안나네요..

shjgkwo   8년 전

아 Suffix Array 로 간당간당하게 p = 문자열 조합패턴의 최대길이, s = 판별해야하는 문자열 최대길이

O(npQ + s + Qslogs) 안에 해결할 수 있을것 같네요 LCP Array로 성능 향상을 기대할 수도 있겠네요..

질문을 바꿔서 suffix array O(nlogn)에 어떻게 구하나요 ㅠㅠ??

koosaga   8년 전

Aho-Corasick 다중 패턴 매칭 알고리즘으로, 구종만님이 쓰신 알고리즘 문제해결전략 2권에 굉장히 잘 설명되어 있습니다. (구글링해도 나올거에요)

제가 옛날에 해싱 풀이를 고민해봤었는데, 쉽지 않았던 걸로 기억합니다 ㅠ

koosaga   8년 전

아호코라식은 선형 시간에 그렇게 어렵지도 않으니 SA보다는 그거 쓰시는 쪽이 나을 거 같아여 ㅋㅋ SA는 잘 몰라서 전 20000...

shjgkwo   8년 전

오 감사합니다 ㅋㅋ! 아호 코라식 알고리즘이었군요

댓글을 작성하려면 로그인해야 합니다.