문자열 목록에서 부분 검색

Question

내 응용 프로그램에서 빠른 검색을 위해 색인으로 사용되는 키 세트가 있습니다.

현재 문자열 전체에서 검색 할 수있는 부분 문자열을 검색 할 수있는 최대 유연성이있을 것입니다. 물론이 작업을 수행하는 순진한 방법은 목록의 모든 문자열을 반복하고 하위 문자열을 찾는 것입니다. 이것은 효과가 있지만 목록이 커지기 시작하면 너무 느립니다.

기수 나무에 대해 조금 읽었지 만 문자열 시작 부분부터 부분 일치를 할 수도 있고 문자열 끝 부분부터 부분 일치를 수행 할 수도 있습니다.

제 질문은 부분 일치 (하나의 큰 문서가 아닌)의 문제를 해결하기 위해 어떤 알고리즘을 사용해야 하나 문자열 목록에 있어야합니다. 정렬 된 문자열 목록을 유지하면이 문제가 더 쉬울까요? 나는 문자열이 같은 길이이지만 가변 길이 문자열의 경우 합리적인 접근법을 생각해 낼 수 없었다면 이것이 더 쉬울 것입니다.

Answer 1

문자열이 모두 있지만 특정 구분 기호가있는 큰 문자열 하나를 보관하면 어떻게 될까요? 인덱스에서 부분 문자열, 부분 문자열을 찾은 다음 분리 문자로 분리하십시오. 이제 문자열에 대한 색인이 생겼습니다. 비연성적 인 문자열을 사용하여 나머지 문자열을 반복하십시오 (또는 모든 정규식을 찾으려면 정규식을 사용하십시오)

Answer 2

접미어 트리 및 접미어 배열은 부분 문자열 일치를 빠르게 수행하려는 경우에 유용합니다.