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

Đề tài: Thuật toán Boyer-Moore

  1. #1
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Mặc định Thuật toán Boyer-Moore

    Trên diễn đàn thấy có chủ đề này rồi, nhưng trong đó chỉ tung source code lên.
    Để đọc về nội dung thuật toán, các bạn quan tâm có thể tham khảo ở đây, do trong đó có nhiều hình ảnh nên mình ngại post qua.
    C Code:
    1. void preBmBc(char *x, int m, int bmBc[]) {
    2.    int i;
    3.  
    4.    for (i = 0; i < ASIZE; ++i)
    5.       bmBc[i] = m;
    6.    for (i = 0; i < m - 1; ++i)
    7.       bmBc[x[i]] = m - i - 1;
    8. }
    9.  
    10.  
    11. void suffixes(char *x, int m, int *suff) {
    12.    int f, g, i;
    13.  
    14.    suff[m - 1] = m;
    15.    g = m - 1;
    16.    for (i = m - 2; i >= 0; --i) {
    17.       if (i > g && suff[i + m - 1 - f] < i - g)
    18.          suff[i] = suff[i + m - 1 - f];
    19.       else {
    20.          if (i < g)
    21.             g = i;
    22.          f = i;
    23.          while (g >= 0 && x[g] == x[g + m - 1 - f])
    24.             --g;
    25.          suff[i] = f - g;
    26.       }
    27.    }
    28. }
    29.  
    30. void preBmGs(char *x, int m, int bmGs[]) {
    31.    int i, j, suff[XSIZE];
    32.  
    33.    suffixes(x, m, suff);
    34.  
    35.    for (i = 0; i < m; ++i)
    36.       bmGs[i] = m;
    37.    j = 0;
    38.    for (i = m - 1; i >= 0; --i)
    39.       if (suff[i] == i + 1)
    40.          for (; j < m - 1 - i; ++j)
    41.             if (bmGs[j] == m)
    42.                bmGs[j] = m - 1 - i;
    43.    for (i = 0; i <= m - 2; ++i)
    44.       bmGs[m - 1 - suff[i]] = m - 1 - i;
    45. }
    46.  
    47.  
    48. void BM(char *x, int m, char *y, int n) {
    49.    int i, j, bmGs[XSIZE], bmBc[ASIZE];
    50.  
    51.    /* Preprocessing */
    52.    preBmGs(x, m, bmGs);
    53.    preBmBc(x, m, bmBc);
    54.  
    55.    /* Searching */
    56.    j = 0;
    57.    while (j <= n - m) {
    58.       for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
    59.       if (i < 0) {
    60.          OUTPUT(j);
    61.          j += bmGs[0];
    62.       }
    63.       else
    64.          j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
    65.    }
    66. }

  2. #2
    Ngày gia nhập
    04 2011
    Bài viết
    54

    Code:
    void preBmBc(char *x, int m, int bmBc[]) {
       int i;
     
       for (i = 0; i < ASIZE; ++i)
          bmBc[i] = m;
       for (i = 0; i < m - 1; ++i)
          bmBc[x[i]] = m - i - 1;
    }
    ASIZE là gì vậy ???

  3. #3
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Trích dẫn Nguyên bản được gửi bởi C Sharp Xem bài viết
    Code:
    void preBmBc(char *x, int m, int bmBc[]) {
       int i;
     
       for (i = 0; i < ASIZE; ++i)
          bmBc[i] = m;
       for (i = 0; i < m - 1; ++i)
          bmBc[x[i]] = m - i - 1;
    }
    ASIZE là gì vậy ???
    Chào bạn!
    ASIZE ở đây được hiểu là mã ANSCII lớn nhất trong mẫu x, thông thường ta cứ để ASIZE=255 cũng được.

  4. #4
    Ngày gia nhập
    04 2011
    Bài viết
    9

    Mặc định demo bằng đồ họa

    hay quá!
    em cũng đang phải làm bài báo cáo về vấn đề này
    nhưng mà thầy bảo làm bằng c++ nhưng phải có phần đồ họa cho dễ nhìn
    mấy huynh có cách nào chỉ em
    Thank nhiu

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

    Unhappy wildcard-các ký tự đại diện

    các anh ơi cho em hỏi thêm với. mình muốn dùng thuật toán Boyemoore để tìm kiếm chuỗi. nhưng trong chuỗi đó có thêm các kỹ tự wild card: ??, *, null, ... thì mình khai báo và dùng vào bài này như thế nào? em ko hiểu chỗ đó quá.

  6. #6
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Mặc định Thuật toán Boyer-Moore

    Trích dẫn Nguyên bản được gửi bởi toiyeuem5a Xem bài viết
    các anh ơi cho em hỏi thêm với. mình muốn dùng thuật toán Boyemoore để tìm kiếm chuỗi. nhưng trong chuỗi đó có thêm các kỹ tự wild card: ??, *, null, ... thì mình khai báo và dùng vào bài này như thế nào? em ko hiểu chỗ đó quá.
    Tôi nghĩ là khó có thể áp dụng được vì tìm kiếm với chuỗi wild card là một thuật toán khác hẳn. Tôi post cho bạn tham khảo thuật toán được cài đặt bằng C++. chuyển sang C code thì thay bool = int, và true = 1, false = 0.
    C++ Code:
    1. bool wild_match(
    2.   const char* pat,
    3.   const char* str
    4. ) {
    5.   bool star = false;
    6.   const char *s;
    7.   const char *p;
    8.  
    9. labs_start:
    10.   for (s = str, p = pat; *s; ++s, ++p) {
    11.     switch (*p) {
    12.     case '?':
    13.       if (*s == '.') {
    14.         if (!star)
    15.           return false;
    16.         ++str;
    17.         goto labs_start;
    18.       }
    19.       break;
    20.     case '*':
    21.       star = true;
    22.       str = s, pat = p;
    23.       if (!*++pat)
    24.         return true;
    25.       goto labs_start;
    26.     default:
    27.       if (
    28.         // Hai dòng bên dưới là so sánh hai kí tự, bạn có thể dùng hàm chuyển
    29.         // đổi về kí tự thường để so sánh, hoặc dùng bảng tìm kiếm.
    30.         // Tuy nhiên, cách dùng bảng nhanh hơn.
    31. //        latin_1::lookup_tables<0>::tolower[static_cast<byte_t>(*s)] !=
    32. //        latin_1::lookup_tables<0>::tolower[static_cast<byte_t>(*p)]
    33.       ) {
    34.         if (!star)
    35.           return false;
    36.         ++str;
    37.         goto labs_start;
    38.       }
    39.       break;
    40.     }
    41.   }
    42.  
    43.   if (*p == '*')
    44.     ++p;
    45.   return (!*p);
    46. }
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

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

    Mặc định WildCard

    bài của bạn Doicanhden hữu ích lắm. ^^

  8. #8
    Ngày gia nhập
    11 2018
    Bài viết
    1

    G.Perelman cho mình hỏi cái OUTPUT với cái MAX là gì v?

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

  1. Code C tìm kiếm chuỗi - Thuật toán Boyer-Moore
    Gửi bởi vie_kainznz trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 01-06-2013, 05:53 PM
  2. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  3. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 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: 16-02-2012, 11:07 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 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