# data[].attributes.body
1.Tô Thành Dũng-2050531200120
2.Hồ Quang Hải- 2050531200137
3.Lưu Văn Tùng-2050531200323
4.Phạm Văn Tài-2050531200304

# data[].attributes.body
String-matching được hiểu là việc tìm một hoặc nhiều xâu mẫu (pattern) xuất hiện trong một văn bản (có thể là rất dài). Ký hiệu xâu mẫu hay xâu cần tìm là X =(x0, x1,..,xm-1) có độ dài m. Văn bản Y =(y0, y1,..,yn-1) có độ dài n. Cả hai xâu được xây dựng từ một tập hữu hạn các ký tự Alphabet ký hiệu là  với kích cỡ là . Như vậy một xâu nhị phân có độ dài n ứng dụng trong mật mã học cũng được xem là một mẫu. Một chuỗi các ký tự ABD độ dài m biểu diễn các chuỗi AND cũng là một mẫu.

Input: Xâu mẫu X =(x0, x1,.., xm), độ dài m. Văn bản Y =(y0, x1,.., yn), độ dài n.

Output: Tất cả vị trí xuất hiện của X trong Y.

# data[].attributes.body
Đặc điểm:

Là thuật toán tìm kiếm mẫu từ trái qua phải

Không có pha chuẩn bị

Bộ nhớ cần dùng cố định

Luôn luôn dịch 1 bước sang phải

Việc so sánh có thể phải dùng trong các trường hợp

Độ phức tạp pha thực thi là O(m x n)

Thuật toán:

for ( j = 0; j <= (n-m); j++)
{ //duyệt từ trái qua phải xâu X
for (i =0; i<m && X[i] == Y[i+j]; i++) ; //Kiểm tra mẫu
if (i>=m) OUTPUT (j);
}

# data[].attributes.body
Thuật toán thực thi việc so sánh từ phải sang trái

Pha cài đặt có độ phức tạp thuật toán và không gian nhớ là O(m+σ)

Pha thực thi có độ phức tạp là O(mxn)

3n kí tự xâu văn bản được so sánh trong trường hợp xấu nhất khi thực thi với mẫu không tuần hoànĐộ phức tạp O(n/m) khi thực thi tốt nhất.

# data[].attributes.body
Thuật toán sẽ quét các ký tự của mẫu (pattern) từ phải sang trái bắt đầu ở phần tử cuối cùng.

Trong trường hợp mis-match (hoặc là trường hợp đã tìm được 1 đoạn khớp với mẫu), nó sẽ dùng 2 hàm được tính toán trước để dịch cửa sổ sang bên phải. Hai hàm dịch chuyển này được gọi là good-suffix shift (còn được biết với cái tên phép dịch chuyển khớp) và bad-character shift (còn được biết với cái tên phép dịch chuyển xuất hiện).

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;
}
void suffixes(char *x, int m, int *suff)
{
     int f, g, i;
     suff[m - 1] = m;
     g = m - 1;
     for (i = m - 2; i >= 0; --i)
     {
       if (i > g && suff[i + m - 1 - f] < i - g)
          suff[i] = suff[i + m - 1 - f];
       else
        {
          if (i < g)
             g = i;
             f = i;
       while (g >= 0 && x[g] == x[g + m - 1 - f])
           g--;
       suff[i] = f - g;
         }
      }
}
void preBmGs(char *x, int m, int bmGs[])
{
    int i, j, suff[XSIZE];
    suffixes(x, m, suff);
    for (i = 0; i < m; ++i)
       bmGs[i] = m;
       j = 0;
    for (i = m - 1; i >= 0; --i)
       if (suff[i] == i + 1)
    for (; j < m - 1 - i; ++j)
       if (bmGs[j] == m)
          bmGs[j] = m - 1 - i;
    for (i = 0; i <= m - 2; ++i)
        bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void BM(char *x, int m, char *y, int n)
{
    int i, j, bmGs[XSIZE], bmBc[ASIZE];
    /* Preprocessing */
    preBmGs(x, m, bmGs);
    preBmBc(x, m, bmBc);
    /* Searching */
    j = 0;
    while (j <= n - m)
    {
       for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
          if (i < 0)
          {
              printf("position is %d",j);
              j += bmGs[0];
           }
          else
               j += max(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
     }
}

# data[].attributes.body
Đặc điểm :

Sử dụng hàm băm

Pha chuẩn bị có độ phức tạp thuật toán và không gian lưu trữ O(m)

Chương trình chạy có độ phức tạp O(m+n)

# data[].attributes.body
Thuật toán:

Hàm băm cung cấp phương thức đơn giản để tránh những con số phức tạp trong việc so sánh những kí tự trong hầu hết các trường hợp thực tế. Thay cho việc kiểm tra từng vị trí trong văn bản nếu như có mẫu xuất hiện, nó chỉ phải kiểm tra những đoạn “gần giống” xâu mẫu. Để kiểm tra sự giống nhau giữa 2 từ sử dụng hàm băm. Giúp cho việc đối chiếu xâu, hàm băm hash:

Có khả năng tính toán được

Đánh giá xâu mức cao.

Hash(y[j+1…j+m]) được tính toán dễ hơn dựa trên hash(y[j…j+m-1]) và hash(y[j+m]).

void KR(char *x, int m, char *y, int n)
{
    int d, hx, hy, i, j;
    /* Preprocessing */
    /* computes d = 2^(m-1) with the left-shift operator */
    for (d = i = 1; i < m; ++i) d = (d<<1);
    for (hy = hx = i = 0; i < m; ++i)
     {
        hx = ((hx<<1) + x[i]);
        hy = ((hy<<1) + y[i]);
      }
    /* Searching */
    j = 0;
    while (j <= n-m)
    {
        if (hx == hy && memcmp(x, y + j, m) == 0)
        printf("position is %d
",j);
        hy = REHASH(y[j], y[j + m], hy);
        ++j;
    }
}

# data[].attributes.body
Sử dụng dụng bad- character

Dễ để cài đặt

Pha cài đặt có độ phức tạp thuật toán là O(m+σ) và độ phức tạp bộ nhớ là O(σ)

Độ phức tạp là O(mxn)

# data[].attributes.body
Quy tắc dịch bad- character được sử dụng trong Boyer Moore không có hiệu quả trong đoạn văn bản kí tự nhỏ, nhưng khi đoạn văn bản là lớn và phải so sánh với mẫu dài, nó thường trong trường hợp bảng bã ASCII và tìm kiếm thông thường trong soạn thảo văn bản, chúng rất h ữu dụng. Sử dụng nó như những kết quả riêng biệt lại rất hiệu quả.

void HORSPOOL(char *x, int m, char *y, int n) {
int j, bmBc[ASIZE];
char c;
/* Preprocessing */
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
c = y[j + m - 1];
if (x[m - 1] == c && memcmp(x, y + j, m - 1) == 0)
printf("position is %d\n",j);
j += bmBc[c];
}
}