빠른 문자열 검색?

Question

필자는 문자열의 벡터를 가지고 있으며 벡터의 각 요소가 지정된 5000 단어 목록에 있는지 확인해야합니다. 두 중첩 루프의 평범한 방법 외에도 C++에서이를 수행하는 더 빠른 방법이 있습니까?

Answer 1

문자열 목록을 std::set에 넣어야합니다. 검색을 위해 최적화 된 데이터 구조입니다. 주어진 엘레멘트가 세트에 있는지 아닌지를 찾는 것은 모든 엔트리를 반복하는 것보다 훨씬 빠른 오퍼레이션이다.

이미 C++ 11을 사용하고있는 경우 해시 테이블로 구현되었으므로 조회가 더 빨라진 std::unordered_set을 사용할 수도 있습니다.

학교/대학용 : 이러한 데이터 구조가 어떻게 더 빠르게 관리되는지 설명 할 수 있도록 준비하십시오. 강사가 왜 그 책을 사용했는지 설명하라고 요청하면 "인터넷에있는 일부 사람들이 나에게 다음과 같이 말했습니다."라고 말하면서 책에 스티커를 적게 넣지는 않습니다.

Answer 2

단어 목록을 std::unordered_set에 넣을 수 있습니다. 그런 다음 벡터의 각 요소에 대해 O (1)의 unordered_set에 있는지 테스트해야합니다. O (n)의 예상되는 복잡성을 갖게됩니다 (예상되는 이유를 보려면 주석을보십시오).

Answer 3

당신은 벡터를 정렬 할 수 있습니다. 그러면 하나의 "루프"(사전이 너무 정렬 됨)를 사용하여이를 해결할 수 있습니다. 즉, O (n)은 정렬 비용을 포함하지 않습니다.

Answer 4

문자열의 벡터가 있고 각 문자열에 하나 이상의 단어가 있고 사전에 벡터가 있고 문자열의 벡터에서 어떤 단어가 사전에 있는지를 결정해야합니까? 문자열의 벡터는 각 단어를 볼 필요가 있기 때문에 짜증이납니다. 먼저 새 벡터를 만들고 각 문자열을 단어로 분할 한 다음 각 단어를 새 벡터로 푸는 것으로 시작합니다. 그런 다음 새 벡터를 정렬하고 std::unique 알고리즘을 통해 실행하여 중복을 제거합니다. 그런 다음 사전을 정렬하십시오. 그런 다음 std::set_intersection을 통해 두 범위를 모두 실행하여 결과를 작성하십시오.