문자열의 배열에서 문자열을 찾는 가장 빠른 알고리즘은 무엇입니까?

Question

이 질문은 알고리즘에 관한 것입니다. 의사 코드 이 같다 : 루프

A = Array of strings; //let's say count(A) = N 
S = String to find; //let's say length(S) = M 

for (Index=0; Index<count(A); Index++) 
    if (A[Index]==S) { 
    print "First occurrence at index\x20"+Index; 
    break; 
    } 

이

가 N 회 (또는 바이트 비교 N * M 회, O (N의 *를 M)) 문자열 비교를 필요로한다. 배열 A에 많은 항목이 있거나 문자열 S가 너무 길 때 이것은 좋지 않습니다.

첫 번째 발생을 찾는 더 좋은 방법은 무엇입니까? O (K * logK)에서의 알고리즘은 괜찮지 만 O (K) 또는 O (logK)에서 가장 좋습니다. 여기서 K는 N 또는 M입니다.

다른 구조를 추가하거나 비교 루프 전에 일부 데이터 처리를 수행합니다.

Answer 1

문자열의 전체 배열을 유한 상태 시스템으로 변환 할 수 있습니다. 여기에서 전환은 문자열의 문자이며 상태를 생성 한 문자열의 가장 작은 인덱스를 상태에 넣습니다. 이는 많은 시간이 소요되며 색인 생성으로 간주 될 수 있습니다.

Answer 2

문자열을 해시 기반 집합에 넣고 지정한 문자열이 집합에 포함되어 있는지 테스트하여 집합이 만들어지면 성능을 일정하게 유지해야합니다.

Answer 3

먼저 O (m * nlogn) 시간이 걸릴 문자열 배열을 정렬 할 수 있습니다. 그리고 A가 정렬 된 후에는 선형 검색 대신 이진 탐색을 수행하여 총 실행 시간을 O (m * logn)로 줄일 수 있습니다.

이 방법의 장점은 구현하기가 쉽다는 것입니다. 예를 들어, 자바에서 당신은 코드의 단지 2 라인이 작업을 수행 할 수 있습니다

Arrays.sort(A); 
int index = Arrays.binarySearch(A, "S"); 

Answer 4

당신은 Self-balancing binary search tree를 사용할 수 있습니다. 대부분의 구현에는 삽입 할 O (log (n))와 검색을 위해 O (log (n))이 있습니다.

값이 크지 않고 값에 대한 해시 함수가 좋으면 해시 기반 집합을 사용하는 것이 더 좋습니다.이 경우 O (1)을 삽입하고 O (1) 검색하기. 그러나 해시 함수가 좋지 않거나 세트가 너무 크면 삽입 할 O (n) 및 검색 O (n)이됩니다.

Answer 5

가능한 한 빨리 검색 할 수있는 가장 좋은 방법은, 당신이 설명대로 배열 를 분류하는 것입니다, 더 가능한 정보를 검색

분류 몇 가지 추론 또는 제한을 허용 것이다 선험적 없을 것 같다 (예 : Quicksort, O (NlogN)), 다음에 이진 검색을 수행합니다.