제공된 문자열에서 다양한 하위 문자열 찾기

Question

내 인터뷰 질문에 대해 얻은 것입니다. 문자열 배열과 문자열 (haystack)이 주어지면 해당 문자열 배열을 사용하는 가장 빠른 알고리즘은 무엇이며 배열의 각 문자열이 건초 더미의 부분 문자열인지 여부를 확인합니다. 가장 빠른 알고리즘은 건초 더미의 모든 부분 문자열을 찾아서 세트에 저장 한 다음 배열의 각 문자열을 세트의 멤버로 검사하는 것이지만 이것이 가장 빠른 방법은 아니라고 알려졌다.

그런 다음 더 세밀한 질문 : 건초 더미에서 부분 문자열이 처음 나타나는 색인을 반환하십시오. 처음 부분이 올바르지 않았기 때문에 나는이 부분과 힘들어했습니다.

Answer 1

알고리즘이 Aho-Corasick 일자리와 비슷합니다.

Answer 2

Suffix tree? 하위 문자열을 테스트하고 시작 색인을 얻을 수 있다고 생각합니다.