Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Lý thuyết tìm kiếm - Tìm kiếm và so khớp chuỗi - Lập trình C

  1. #1
    Ngày gia nhập
    01 2007
    Bài viết
    412

    Lightbulb Lý thuyết tìm kiếm - Tìm kiếm và so khớp chuỗi - Lập trình C

    Một số thuật toán cơ bản tìm kiếm chuỗi
    a) Thuật toán Brute Force
    Thuật toán Brute Force so sánh mẫu (Pattern) tìm kiếm với văn bản (Text), mỗi lần 1 ký tự, cho đến khi các ký tự không khớp được tìm thấy
    Thuật toán có thể được thiết kế sao cho nó sẽ dừng khi gặp sự xuất hiện đầu tiên của mẫu trong văn bản hoặc cho đến khi đã xét đến cuối văn bản

    o Thuật toán

    Input: String mẫu P với m ký tự
    Ouput:Vị trí chuỗi mẫu P trong T hoặc báo không có

    do
    if (text letter == pattern letter)
    so sánh text letter kế với pattern letter kế
    else
    chuyển pattern dịch sang phải 1 letter
    until (tìm thấy toàn bộ pattern hoặc đến cuối text)

    o Độ phức tạp của thuật toán Brute Force:
    Giả sử kích thước của mẫu là M ký tự và text có N ký tự
    § Trường hợp tốt nhất 1: mẫu xuất hiện ngay đầu text
    Độ phức tạp trong trường hợp tốt nhất 1: O(M)
    § Trường hợp tốt nhất 2: mẫu không xuất hiện trong text
    Độ phức tạp trong trường hợp tốt nhất 2: O(N)
    § Trường hợp xấu nhất: so sánh mẫu với mọi chuỗi con chiều dài M trong text
    Ø Tổng số phép so sánh: M (N-M+1)
    Ø Độ phức tạp trong trường hợp xấu nhất: O(MN)

    o Cài đặt thuật toán

    C Code:
    1. char *Brute_Force(char *source, char *substr, int *k)
    2.   {
    3.      int  i = 0, j = 0, m, n;
    4.      n = strlen(source) - 1;
    5.      m = strlen(substr) - 1;
    6.      do {
    7.        if (source == substr[j])
    8.        {
    9.          i++;
    10.          j++;
    11.        }
    12.        else
    13.        {
    14.           i = i - j + 2;
    15.           j = 0;
    16.        }
    17.      } while (j <= m && i <= n);
    18.      if (j > m)
    19.      {
    20.        *k = i - m - 1;
    21.        return source + i - m - 1;
    22.      }
    23.      else
    24.        return NULL;
    25.   }

    b) Thuật toán Knuth Morris Pratt
    Thuật toán được phát minh năm 1977 bởi hai giáo sư của ĐH ********, Hoa Kỳ (1 trong số ít các trường đại học xếp hàng số một về khoa học máy tính trên thế giới cùng với MIT, CMU cũng của Hoa Kỳ và Cambridge của Anh) Donal Knuth và Vaughan Ronald Pratt, Knuth (giải Turing năm 1971) còn rất nổi tiếng với cuốn sách Nghệ thuật lập trình (The Art of Computer Programming) hiện nay đã có đến tập 6, 3 tập đầu tiên đã có xuất bản ở Việt Nam, cuốn sách gối đầu giường cho bất kỳ lập trình viên nói riêng và những ai yêu thích lập trình máy tính nói chung trên thế giới. Thuật toán này còn có tên là KMP lấy tên viết tắt của ba người phát minh ra nó, chữ “M” là chỉ giáo sư J.H.Morris, một người cũng rất nổi tiếng trong khoa học máy tính.

    Ý tưởng chính của phương pháp này như sau : trong quá trình tìm kiếm vị trí của mẫu P trong xâu gốc T, nếu tìm thấy một vị trí sai ta chuyển sang vị trí tìm kiếm tiếp theo và quá trình tìm kiếm sau này sẽ được tận dụng thông tin từ quá trình tìm kiếm trước để không phải xét các trường hợp không cần thiết.

    Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên được phát hiện ra, nó dựa trên thuật toán brute force với ý tưởng lợi dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán Brute Force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả. Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại.

    Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x và y[j+i-1].
    Khi đó x[1…i]=y[j…i+j-1]=u và a=x¹y[i+j]=b. Với trường hợp này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ dài lớn nhất.
    Thuật toán Knuth-Morris-Pratt sử dụng mảng Next để lưu trữ độ dài lớn nhất của xâu v trong trường hợp xâu u=x[1…i-1]. Mảng này có thể tính trước với chi phí về thời gian là [I]O[I](m) (việc tính mảng Next thực chất là một bài toán qui hoạch động một chiều).
    Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là [I]O[I](m+n) với nhiều nhất là 2n-1 lần số lần so sánh ký tự trong quá trình tìm kiếm.

    C Code:
    1. int KMP(char *source, char *find)
    2.   {
    3.     int next[MAX], i = 0, len, j=-1, lensource;
    4.    
    5.     len = strlen(find);
    6.     lensource = strlen(source);
    7.     next[0] = -1;
    8.     do {
    9.       if (j == -1 || find[i] == find[j])
    10.       {
    11.         i++;
    12.         j++;
    13.         next[i] = j;
    14.       }
    15.       else
    16.         j = next[j];
    17.     } while (i < len-1);
    18.     i = j = 0;
    19.     do {
    20.       if (j==0 || source[i] == find[j])
    21.       {
    22.         i++;
    23.         j++;
    24.       }
    25.       else
    26.         j = next[j];
    27.     } while (j<len && i<lensource);
    28.     if (j>=len)
    29.       return i-len;
    30.     else
    31.       return -1;
    32.   }

  2. #2
    Ngày gia nhập
    01 2007
    Bài viết
    412

    c) Thuật toán Boyer Moore
    Thuật toán Boyer Moore là thuật toán có tìm kiếm chuỗi rất có hiệu quả trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong các chương trình soạn thảo văn bản.

    Khác với thuật toán Knuth-Morris-Pratt (KMP), thuật toán Boyer-Moore kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi Trong thuật toán này có hai cách dịch của sổ:

    Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao cho những phần đã so sánh trong lần trước khớp với những phần giống nó trong lần sau.
    Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra sự khác nhau, lúc đó x[i+1…m]=y[i+j...j+m-1]=u và a=x[i]y[i+j-1]=b khi đó thuật toán sẽ dịch cửa sổ sao cho đoạn u=y[i+j…j+m-1] giống với một đoạn mới trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất)
    Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu.
    Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j-1] ta sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất)
    Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp
    Trong hai cách dịch thuật toán sẽ chọn cách dịch có lợi nhất.

    C Code:
    1. int BoyerMoore(char *source, char *find)
    2. {
    3.   int skip[MAX], i = 0, len, j=-1, lensource;
    4.  
    5.   len = strlen(find);
    6.   lensource = strlen(source);
    7.   for (i=0; i<MAX; i++)
    8.     skip[i] = len-1;
    9.   for (i=0; i<len; i++)
    10.     if (skip[find[i]] == len-1)
    11.        skip[find[i]] = len-i-1;
    12.  
    13.   i = j = len-1;
    14.   do {
    15.     if (source[i] == find[j])
    16.     {
    17.       i--;
    18.       j--;
    19.     }
    20.     else
    21.     {
    22.       if (len-j+1 > skip[source[i]])
    23.         i += len-j+1;
    24.       else
    25.         i += skip[source[i]];
    26.       j = len-1;
    27.     }
    28.   } while (j>0 && i<lensource);
    29.  
    30.   if (j<=0)
    31.     return i;
    32.   else
    33.     return -1;
    34. }

    Thuật toán Boyer-Moore có thể đạt tới chi phí O(n/m) là nhờ có cách dịch thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không khớp” cài đặt vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có nhiều thuật toán khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử dụng cách dịch này.

    Tuy nhiên chi phí thuật toán của Boyer-Moore là O(m*n) vì cách dịch thứ nhất của thuật toán này không phân tích triệt để các thông tin của những lần thử trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài thuật toán đã cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán Boyer-Moore là tuyến tính.

    So khớp chuỗi (String Matchching)
    Ý nghĩa của ký tự đại diện (wildcard)
    Có hai ký tự wildcard thông thường là ? và * .
    • Dấu hỏi đại diện cho một ký tự duy nhất bất kỳ.
    • Dấu sao (*) đại diện cho nhiều ký tự bất kỳ hoặc không có ký tự nào cả.
    Bạn hãy quan sát vài ví dụ dưới đây:
    Mẫu Chuỗi so sánh Kết quả
    w?ldcard wildcard khớp
    w?ldcard waldcard khớp
    w*ldcard wldcard khớp (không có ký tự)
    w*ldcard willdcard khớp (có hai ký tự)
    w*ldcard* wldcards khớp

    Thuật toán

    Việc xử lý dấu hỏi khá đơn giản. Nếu không có dấu * trong chuỗi mẫu, ta chỉ cần duyệt lần lượt qua từng cặp ký tự trong chuỗi mẫu và chuỗi cần so sánh. Nếu gặp ký tự ? bên chuỗi mẫu thì ta luôn luôn bỏ qua (coi như cặp ký tự ở hai chuỗi là khớp). Ta chỉ cần lưu ý là hai chuỗi phải có cùng chiều dài.

    C Code:
    1. int Match(char *pattern, char *str)
    2. {
    3.   int i;
    4.   int j;
    5.   for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++)
    6.   {
    7.     if ( pattern[i] == '?')
    8.       continue;
    9.     else if (pattern[i] != str[j])
    10.       return 0;
    11.   }
    12.   if ( (i==strlen(pattern)) && (j == strlen(str)) )
    13.     return 1;
    14.   else
    15.     return 0;
    16. }

    Bước tiếp theo là xử lý trường hợp dấu *. Vì dấu sao đại diện cho nhiều hoặc không ký tự nào nên việc so khớp có vẻ rắc rối. Tuy nhiên, nếu ta xử lý theo kiểu đệ quy thì vấn đề sẽ dễ hiểu và đơn giản hơn. Mục tiêu của đệ quy là đưa bài toán về một bài toán cùng dạng nhưng độ phức tạp giảm dần cho đến khi đạt đến những bài toán cơ bản, dễ giải quyết.

    Việc xử lý dấu * chỉ có nghĩa khi phần đầu của chuỗi mẫu và chuỗi so sánh đã khớp với nhau, nếu không thì ta đã có thể kết luận ngay là không khớp. Do vậy để đơn giản mà không làm mất tính tổng quát, ta có thể giả sử chuỗi mẫu bắt đầu bằng ký tự *
    Như vậy chuỗi mẫu sẽ gồm 2 phần: dấu * và phần còn lại. Chuỗi cần so sánh cũng sẽ có 2 phần tương ứng: ký tự tại vị trí dấu * và phần còn lại.

    Có 3 trường hợp sau dẫn đến kết quả là chuỗi mẫu và chuỗi so sánh khớp nhau:
    • Dấu * là ký tự duy nhất của chuỗi mẫu. Đây là trường hợp hiển nhiên.
    • Phần còn lại của chuỗi mẫu khớp với toàn bộ chuỗi so sánh (tính chất dấu * đại diện cho không có ký tự nào)

    • Toàn bộ chuỗi mẫu khớp với phần còn lại của chuỗi so sánh (tính chất dấu * đại diện cho 1 hoặc nhiều ký tự)

    Hai trường hợp (b) và (c) sẽ dẫn đến việc thực hiện lại bài toán so khớp giữa chuỗi con của chuỗi mẫu và chuỗi con của chuỗi so sánh. Bạn dễ dàng thấy được tính dừng của phép đệ quy này vì mỗi lần đệ quy ta đều giảm chiều dài của chuỗi mẫu hoặc chuỗi so sánh đi một ký tự.

    Nếu cả 3 trường hợp trên đều không thỏa thì chuỗi mẫu và chuỗi so sánh không khớp nhau.Bây giờ ta chỉ cần sửa lại chương trình ban đầu để đưa lời gọi đệ quy vào là xong

    C Code:
    1. int Match(char *pattern, char *str)
    2. {
    3.   int i;
    4.   int j;
    5.   for (i=0, j=0;( i<strlen(pattern) ) && ( j <strlen(str)) ;i++,j++)
    6.   {
    7.     if ( pattern[i] == '?')
    8.       continue;
    9.     else if (pattern[i] == '*')
    10.     {
    11.       if (i==strlen(pattern)-1) return 1;
    12.       else if (Match(&pattern[i+1], &str[i])) return 1;
    13.       else if (Match(&pattern[i], &str[j+1])) return 1;
    14.       else return 0;
    15.     }
    16.     else if (pattern[i] != str[j])
    17.     return 0;
    18.   }
    19.   if ( (i==strlen(pattern)) && (j == strlen(str)) )
    20.     return 1;
    21.   else
    22.     return 0;
    23. }

  3. #3
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Angry Re:sửa lai thuật toán Brute_Force Tìm kiếm và so khớp chuỗi

    trong thuật toán Brute_Force khi debug mình thấy có một chỗ sai, và một chỗ thừa không cần thiết. mình xin sửa lại như sau

    C Code:
    1. int Brute_Force(char *source, char *substr)
    2. {
    3.     int  i = 0, j = 0, m, n;
    4.     n = strlen(source) - 1;
    5.     m = strlen(substr) - 1;
    6.     do {
    7.         if (source[i] == substr[j])
    8.         {
    9.             i++;
    10.             j++;
    11.         }
    12.         else
    13.         {
    14.             i = i - j + 1;// code cũ là i = i-j+2 như thế i sẽ tăng lên 2
    15. //sau mỗi lần lặp và ký tự đó bị bỏ qua ko so sánh dẫn đến thuật toán sai
    16.             j = 0;
    17.         }
    18.     } while (j <= m && i <= n);
    19.     if (j > m)
    20.     {
    21.         // chỗ này mình bỏ *k = i-m-1; vì thấy biến k ko hề được sử dụng
    22.                 //  như vậy là thừa
    23.         return i - m - 1;
    24.     }
    25.     else
    26.         return NULL;
    27. }

    hàm trả về giá trị int thay vì char * để cho biết vị trí xuất hiện đầu tiên của chuỗi cần kiểm tra.

    Vui lòng để code vào tag code. Đọc Nội quy để biết thêm chi tiết
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 07:52 PM. Lý do: Nhắc nhở

  4. #4
    Ngày gia nhập
    03 2008
    Bài viết
    57

    cách 1:

    C++ Code:
    1. bool BruteFore(char *x, int m, char *y, int n)
    2. {
    3.     int i,j;
    4.     for( j =0; j<= n -m ; ++j)
    5.     {
    6.         for( i = 0; i<m && x[i] == y[i+j]; )
    7.         {
    8.             i++;
    9.             if(i==m)
    10.             {
    11.                 return true;
    12.             }
    13.         }
    14.     }
    15.     return false;
    16. }

    cách 2:
    C++ Code:
    1. bool newBruteForce(char *x, int m, char *y, int n)
    2. {
    3.     char *yb;
    4.     for(yb = y; (yb - y)<= n-m ; ++yb)
    5.     {
    6.         if(memcmp(x,yb,m) == 0)
    7.             return true;
    8.     }
    9.     return false;
    10. }
    trong đó x là chuỗi cần kiểm tra, y là chuỗi mẹ dùng để kiểm tra

    cách 3:
    C++ Code:
    1. bool NewBruteForce(char *p, char*t)
    2. {
    3.     if( (strlen(t) == 0 ) || ( strlen(p) == 0 ) || ( strlen(p) > strlen(t)))
    4.         return false;
    5.     int stop =  strlen(t) - strlen(p);
    6.     int start = 0;
    7.     int j = start;
    8.     for(int i = start; i <= stop ; )
    9.     {
    10.         if( p[j] == t[i+j])
    11.             j++;
    12.         else
    13.         {
    14.             j = start;
    15.             i++;
    16.         }
    17.         if( j == strlen(p))
    18.             return true;
    19.     }
    20.     return false;
    21. }

    cách 4: (do mình nghĩ ra)

    C++ Code:
    1. void initNext(char *p, char *t, vector<int> &Next)
    2. {
    3.     int i; 
    4.     int n = strlen(t);
    5.     int m = strlen(m);
    6.     for( i =0; i<= n - m; i++)
    7.         if(t[i] == p[0])
    8.             Next.push_back(i);
    9. }
    10.  
    11. int NTL(char *p, char *t)
    12. {
    13.     int i,j;
    14.     vector<int> next;
    15.     initNext(p,t,next);
    16.     if(next.size() == 0)
    17.         return -1; 
    18.     if(strlen(p) == 1)
    19.         return next[0];
    20.     for( int n =0; n < next.size(); n++)   
    21.     {
    22.         i = next[n] +1;
    23.         j =1;
    24.         while(p[j++] == t[i++])
    25.             if(j == strlen(p))
    26.                 return next[n];
    27.     }
    28.     return -1;
    29. }
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 12:41 PM.

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Nếu được mong bạn thanhluan07 có thể nhín ra chút thời gian để ghi ra thêm giải thuật cho các bạn khác dễ theo dõi hơn được không ?, đọc code không thì cũng hơi bị oải nhỉ T_T. Anyways thanks for your contribution !

  6. #6
    Ngày gia nhập
    03 2008
    Bài viết
    57

    Wink Re:Giải thuật Brute_Force chi tiết

    Code:
    Mục đích: Kiểm tra một chuỗi có nằm trong một chuỗi khác hay không.
    Giả sử xét xem chuỗi P có xuất hiện trong chuỗi T hay không.
    Phương pháp chung:
            So sánh từng ký tự trong P với từng ký tự trong T. 
    Bắt đầu từng ký tự trong P so sánh cho đến hết chuỗi P. 
    Trong quá trình so sánh nếu thấy sai khác giữa P và T 
    thì bắt đầu lại từ đầu P ,và đối với T là ký tự kế tiếp ký tự của lần so sánh trước.
    
    Giải thuật: ( mã giả )
    /Nhập chuỗi chính T
    Nhập chuỗi cần xét P
    IF ((  len (P) = 0) OR ( len (T) = 0 ) OR (  len (P) > len (T) )
     // len : chiều dài chuỗi 
    	P không xuất hiện trong T
    ELSE
    	Tính vị trí dừng STOP =  len(T) – len(P)
    	Vị trí bắt đầu so sánh START = 0
    // ta cần vị trí dừng vì ra khỏi STOP 
    //chiều dài P lớn hơn chiều dài đoạn T còn lại thì dĩ nhiên P không thuộc T
    So sánh các ký tự giữa P và T bắt đầu từ START
    IF ( các ký tự đều giống nhau )
    	P có xuất hiện trong T
    ELSE
    	Tăng START lên 1
    Dừng khi P xuất hiện trong T hoặc START > STOP
    
    Ví dụ:
    T = “I LIKE COMPUTER”	 n = len(T) = 14
    P = “LIKE”		 m = len(P) = 4
    
    start = 0
    stop = n-m = 10
    
    Bước 1:    I LIKE COMPUTER  i = start = 0
               LIKE             j = 0
               P[j] = 'L' != T[i+j] = 'I'
    ----> tăng i lên 1 ( ký tự tiếp theo trong T)
            j = 0;( trở về đầu chuỗi P so sánh lại từ đầu P hay P dịch sang phải 1 ký tự.
    Bước 2:   I LIKE COMPUTER         i = 1  
               LIKE                   j = 0
         p[j] = 'L' != T[i] = ' '
    ---> tăng i lên một, j = 0
    Bước 3:    I LIKE COMPUTER       i = 2    
                 LIKE                j = 0
           p[j]  == T[i+j] ='L'
    ----> tăng j lên một,
     không tăng i vì ta đang xét T[i+j]. chỉ khi nào có sự sai khác ta mới tăng i lên một
    
    Bước 4:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 1
               p[j] == T[i+j] = 'I'
    -----> tăng j lên một
    Bước 5:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 2
               p[j] == T[i+j] = 'K'
    -----> tăng j lên một
    Bước 6:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 3
               p[j] == T[i+j] = 'I'
    -----> tăng j lên một -----> j = 4 = m : hết chuỗi P ------> P có xuất hiện trong T
    
     ----> Xuất ra vị trí i = 2 là vị trí xuất hiện đầu tiên của P trong T
    Đã được chỉnh sửa lần cuối bởi thanhluan07 : 05-03-2008 lúc 02:39 PM.

  7. #7
    Ngày gia nhập
    03 2013
    Bài viết
    8

    Mặc định BoyerMoore

    Trích dẫn Nguyên bản được gửi bởi thanhluan07 Xem bài viết
    Code:
    Mục đích: Kiểm tra một chuỗi có nằm trong một chuỗi khác hay không.
    Giả sử xét xem chuỗi P có xuất hiện trong chuỗi T hay không.
    Phương pháp chung:
            So sánh từng ký tự trong P với từng ký tự trong T. 
    Bắt đầu từng ký tự trong P so sánh cho đến hết chuỗi P. 
    Trong quá trình so sánh nếu thấy sai khác giữa P và T 
    thì bắt đầu lại từ đầu P ,và đối với T là ký tự kế tiếp ký tự của lần so sánh trước.
    
    Giải thuật: ( mã giả )
    /Nhập chuỗi chính T
    Nhập chuỗi cần xét P
    IF ((  len (P) = 0) OR ( len (T) = 0 ) OR (  len (P) > len (T) )
     // len : chiều dài chuỗi 
    	P không xuất hiện trong T
    ELSE
    	Tính vị trí dừng STOP =  len(T) – len(P)
    	Vị trí bắt đầu so sánh START = 0
    // ta cần vị trí dừng vì ra khỏi STOP 
    //chiều dài P lớn hơn chiều dài đoạn T còn lại thì dĩ nhiên P không thuộc T
    So sánh các ký tự giữa P và T bắt đầu từ START
    IF ( các ký tự đều giống nhau )
    	P có xuất hiện trong T
    ELSE
    	Tăng START lên 1
    Dừng khi P xuất hiện trong T hoặc START > STOP
    
    Ví dụ:
    T = “I LIKE COMPUTER”	 n = len(T) = 14
    P = “LIKE”		 m = len(P) = 4
    
    start = 0
    stop = n-m = 10
    
    Bước 1:    I LIKE COMPUTER  i = start = 0
               LIKE             j = 0
               P[j] = 'L' != T[i+j] = 'I'
    ----> tăng i lên 1 ( ký tự tiếp theo trong T)
            j = 0;( trở về đầu chuỗi P so sánh lại từ đầu P hay P dịch sang phải 1 ký tự.
    Bước 2:   I LIKE COMPUTER         i = 1  
               LIKE                   j = 0
         p[j] = 'L' != T[i] = ' '
    ---> tăng i lên một, j = 0
    Bước 3:    I LIKE COMPUTER       i = 2    
                 LIKE                j = 0
           p[j]  == T[i+j] ='L'
    ----> tăng j lên một,
     không tăng i vì ta đang xét T[i+j]. chỉ khi nào có sự sai khác ta mới tăng i lên một
    
    Bước 4:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 1
               p[j] == T[i+j] = 'I'
    -----> tăng j lên một
    Bước 5:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 2
               p[j] == T[i+j] = 'K'
    -----> tăng j lên một
    Bước 6:    I LIKE COMPUTER          i = 2
                 LIKE                   j = 3
               p[j] == T[i+j] = 'I'
    -----> tăng j lên một -----> j = 4 = m : hết chuỗi P ------> P có xuất hiện trong T
    
     ----> Xuất ra vị trí i = 2 là vị trí xuất hiện đầu tiên của P trong T
    thuật toán BoyerMoore mà cũng được giải thích và ví dụ như thế này thì có phải là hay và rất dễ hiểu không nhỉ.

Các đề tài tương tự

  1. Các giải thuật tìm kiếm - Lý thuyết và cài đặt trên C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 24-02-2015, 05:21 PM
  2. [Kiếm Thế] Kiếm Thế Ngạo Thiên Kiếm Chạy Thử Nghiệm vào 10h ngày 15/09
    Gửi bởi c0jskull trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 5
    Bài viết cuối: 29-09-2013, 10:45 AM
  3. [Kiếm Thế] Kiếm Thế Kiếm Linh Chạy Thử Nghiệm vào 10h ngày 4/7
    Gửi bởi c0jskull trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 05-07-2013, 12:16 PM
  4. Lý thuyết tìm kiếm | Bảng băm ( hash table )
    Gửi bởi hailoc12 trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 5
    Bài viết cuối: 16-10-2012, 10:50 AM
  5. Các bài Kiến thức Thương hiệu, lý thuyết và thực hành tại Phòng marketing
    Gửi bởi myvietbrand trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 3
    Bài viết cuối: 22-09-2012, 05:07 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn