Thuật toán nhanh nhất để tìm một chuỗi trong một chuỗi các chuỗi?

Question

Câu hỏi này chỉ đơn thuần là về thuật toán. Trong mã giả là như thế này:

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ày cho vòng lặp đòi hỏi so sánh chuỗi N lần (hoặc byte so sánh N * M lần, O (N * M)). Điều này là xấu khi mảng A có nhiều mục hoặc khi chuỗi S quá dài.

Bất kỳ phương pháp nào tốt hơn để tìm ra sự xuất hiện đầu tiên? Một số thuật toán tại O (K * logK) là OK, nhưng thích hợp hơn ở O (K) hoặc tốt nhất tại O (logK), trong đó K là N hoặc M.

Tôi không ngại thêm vào một số cấu trúc khác hoặc thực hiện một số xử lý dữ liệu trước vòng lặp so sánh.

Answer 1

Bạn có thể chuyển đổi toàn bộ chuỗi các chuỗi thành một máy trạng thái hữu hạn, trong đó chuyển tiếp là các ký tự của các chuỗi và đặt chỉ mục nhỏ nhất của các chuỗi đã tạo trạng thái vào trạng thái. Quá trình này mất rất nhiều thời gian và có thể được xem là lập chỉ mục.

Answer 2

Đặt chuỗi thành bộ băm dựa trên và kiểm tra xem chuỗi đã cho có được đặt trong bộ hay không sẽ cung cấp cho bạn hiệu suất liên tục nhiều hơn hoặc ít hơn khi bộ được tạo.

Answer 3

Trước tiên, bạn có thể sắp xếp chuỗi các chuỗi, sẽ mất thời gian O (m * nlogn). Và sau khi sắp xếp A, bạn có thể thực hiện tìm kiếm nhị phân thay vì tìm kiếm tuyến tính, có thể giảm tổng thời gian chạy xuống O (m * logn).

Ưu điểm của phương pháp này là nó khá dễ thực hiện. Ví dụ: trong Java, bạn có thể thực hiện điều này chỉ với 2 dòng mã:

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

Answer 4

Bạn có thể sử dụng Self-balancing binary search tree. Hầu hết các triển khai có O (log (n)) để chèn, và O (log (n)) để tìm kiếm.

Nếu bộ của bạn không lớn và bạn có hàm băm tốt cho giá trị của mình, bộ băm dựa trên là giải pháp tốt hơn, vì trong trường hợp đó bạn sẽ có O (1) để chèn và O (1) tìm kiếm. Nhưng nếu hàm băm của bạn là xấu hoặc tập của bạn quá lớn, nó sẽ là O (n) để chèn và O (n) để tìm kiếm.

Answer 5

Cách tốt nhất để tìm kiếm càng nhanh càng tốt, là phải có mảng được sắp xếp Như bạn mô tả, có vẻ là không có thông tin có thể tiên nghiệm mà sẽ cho phép một số chẩn đoán hoặc hạn chế trong việc tìm kiếm

Sắp xếp mảng đầu tiên (Quicksort ví dụ, O (NlogN)), và tìm kiếm nhị phân tiếp theo O (log (N))