Thuật toán đối sánh chuỗi tốc độ cao

Question

Tôi cơ bản đo điểm chuẩn một số thuật toán khớp chuỗi tốc độ cao, tôi đã gặp một vài thuật toán.

1. ngược Dawg không xác định (Đạo từ đồ thị acyclic) thuật toán Matching bởi Gonzalo Navarro và Mathieu Raffinot. Xem "Một cách tiếp cận Bit-Song song với Suffix automata: Nhanh chóng mở rộng chuỗi Matching" phiên bản cải tiến

2. Horspool của của Boyer-Moore Chuỗi thuật toán tìm kiếm. Xem "nhanh chóng tìm kiếm thực tế trong chuỗi"

3. Shift-Hoặc thuật toán với sai lệch

4. KMP

Có bất kỳ thuật toán phù hợp tốt hơn chuỗi tốc độ cao khác tôi có thể thử?

Edit: Có một thread trong dòng tương tự, trong đó có tài liệu tham khảo tốt quá

Answer 1

Bạn cũng có thể thử

• Z Algorithm: Trong một số cách mặc gọn gàng hơn KMP
• Aho Corasick: Trie dựa và ban đầu được sử dụng cho fgrep
• Rabin Karp: Hash dựa

Answer 2

Kết hợp chuỗi hai chiều là, theo hiểu biết của tôi, thuật toán đa năng tốt nhất cho kết hợp chuỗi. Nó có độ phức tạp xấu nhất tuyến tính, sử dụng không gian cố định và không quay lại quá nhiều so với mức cần thiết. Và lý thuyết đằng sau nó rất hay.

Nếu bạn biết người dùng của bạn không bị giật, kết hợp chuỗi ngây thơ được tối ưu hóa cho kiến ​​trúc của bạn sẽ giành được "kim" ngắn trong khi biến thể Boyer-Moore sẽ bắt đầu thực sự thực hiện điều tuyến dưới cho "kim" dài. Tuy nhiên, kết hợp chuỗi ngây thơ có một trường hợp xấu nhất bậc hai và Boyer-Moore có thể được thực hiện để kiểm tra tất cả các ký tự trong đầu vào. Các bảng phụ cần thiết để xử lý các sự không phù hợp thực sự mang một hình phạt đáng ngạc nhiên nghiêm trọng đối với kết hợp chuỗi hai chiều.

Answer 3

import java.util.Scanner; 

public class StringMatch { 

static int temp,i=0,j=0; static boolean flag=true,matcher=false; 

    static String str=null,mstr=null;static char astr[],amstr[]; 

     static void getter(){ 
     Scanner sc = new Scanner(System.in); 
     str = sc.nextLine(); 
     //String str="today is Monday"; 
     astr=str.toCharArray(); 
     mstr = sc.nextLine(); 
     //String mstr="is"; 
     amstr=mstr.toCharArray(); 
    } 
    static void stringMatch(){ 
     while(i<astr.length){ 
      if(astr[i]==amstr[j]){ 
      while((j!=amstr.length)&&flag){temp=i; 
       if(astr[i]!=amstr[j]) {flag=false;matcher=false;} 
       else{matcher=true;} 
       i++;j++; 
       //System.out.println(i+"\t"+j); 
      }if(matcher==true)break;i=temp;}i++;j=0;flag=true; 

     } 
     if(matcher==true) {System.out.println("true");} 
     else {System.out.println("false");} 
    } 
    public static void main(String[] args) { 

    StringMatch.getter(); 
    StringMatch.stringMatch(); 

    } 
}