9250번 - 문자열 집합 판별
별다른 뾰족한 수가 안나네요..
아 Suffix Array 로 간당간당하게 p = 문자열 조합패턴의 최대길이, s = 판별해야하는 문자열 최대길이
O(npQ + s + Qslogs) 안에 해결할 수 있을것 같네요 LCP Array로 성능 향상을 기대할 수도 있겠네요..
질문을 바꿔서 suffix array O(nlogn)에 어떻게 구하나요 ㅠㅠ??
Aho-Corasick 다중 패턴 매칭 알고리즘으로, 구종만님이 쓰신 알고리즘 문제해결전략 2권에 굉장히 잘 설명되어 있습니다. (구글링해도 나올거에요)
제가 옛날에 해싱 풀이를 고민해봤었는데, 쉽지 않았던 걸로 기억합니다 ㅠ
아호코라식은 선형 시간에 그렇게 어렵지도 않으니 SA보다는 그거 쓰시는 쪽이 나을 거 같아여 ㅋㅋ SA는 잘 몰라서 전 20000...
오 감사합니다 ㅋㅋ! 아호 코라식 알고리즘이었군요
댓글을 작성하려면 로그인해야 합니다.
shjgkwo 8년 전 1
별다른 뾰족한 수가 안나네요..