STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ

    Naive String Search - Tìm Kiếm Kiểu Thơ Ngây

    Hướng dẫn tìm kiếm một chuỗi kí tự trong một đoạn văn bản bằng giải thuật Naive String Search qua code mẫu.
    16/08/2015
    17/08/2020
    3 phút đọc
    Naive String Search - Tìm Kiếm Kiểu Thơ Ngây

    Naive String Search

    Naive String Search (Naïve Pattern Searching) hay tìm kiếm 1 cách chính xác là 1 giải thuật trong nhiều giải thuật tìm kiếm 1 mẫu chuỗi trong 1 đoạn văn.

    Ý tưởng

    Ứng dụng thuật toán tìm kiếm tuần tự trên chuỗi:

    • Dịch chuyển chuỗi cần tìm Pattern để so với từng mẫu nhỏ trong đoạn văn Target.
      • Tại 1 vị trí i của Target, tiến hành so sánh Pattern với chuỗi con tính từ vị trí i của TargetPattern.
        • Nếu chuỗi con của Target tính từ vị trí i bằng với chuỗi Pattern (bằng từng cặp ký tự), trả về i là vị trí cần tìm.
    • Đến cuối chuỗi vẫn không tìm được chuỗi giống nhau nào (i chưa được tìm thấy ở phép thử trên), trả về giá trị -1.
    Tìm kiếm chuỗi chính xác

    Code mẫu Naive String Search

    Để dễ dàng hơn trong hiện thực giải thuật chia thành các hàm sau:

    • Hàm hỗ trợ lấy độ dài chuỗi: size_t GetStringLength(char* str).
    • Hàm so sánh 2 chuỗi: bool CompareString(char* str1, char* str2).
    • Hàm chính - tìm kiếm vị trí pattern trong target: size_t NaiveStringSearch(char* target, char* pattern).
    #include <iostream>
    using namespace std;
    
    size_t GetStringLength(char* str)
    {
        size_t len = 0;
        while (*str != '\0') {
            ++str;
            ++len;
        }
        return len;
    }
    
    bool CompareString(char* str1, char* str2)
    {
        while (*str1 != '\0' && *str2 != '\0')
        {
            if (*str1 != *str2)
                return false;
            str1++;
            str2++;
        }
        return true;
    }
    
    size_t NaiveStringSearch(char* target, char* pattern)
    {
        int tLength = GetStringLength(target);
        int pLength = GetStringLength(pattern);
    
        for (int i = 0; i < tLength - pLength + 1; ++i)
        {
            if (CompareString(target + i, pattern))
                return i;
        }
    
        return (size_t)-1;
    }
    
    int main()
    { char target[] = "Computer need RAM and CPU."; char pattern[] = "RAM"; size_t pos = NaiveStringSearch(target, pattern); if (pos == (size_t)-1) { cout << "Khong tim thay pattern trong target"; } else { cout << "Tim thay pattern trong target o vi tri: " << pos; } return 0; }

    Lời bình code

    i < tLength - pLength + 1: không cần tìm kiếm từ đầu cho đến vị trí cuối cùng của targetpattern chỉ cần đặt ở vị trí sao cho điểm cuối cùng của target trùng với điểm cuối cùng của pattern.

    if (CompareString(target + i, pattern)): đây là kỹ thuật chia để trị, không để logic quá phức tạp nên không cần thiết hiện thực phần so sánh chuỗi lồng vào phần hiện thực NaiveStringSearch, dẫn đến vòng lặp lồng vào vòng lặp với nhiều biến làm tăng độ phức tạp. Tuy nhiên, nếu cần tối ưu về thời gian thực thi, có thể phải cải tiến bằng cách viết cả phần hiện thực của CompareString vào NaiveStringSearch.

    Đánh giá

    • Độ phức tạp trung bình của thuật toán là O(m + n) (với n là độ dài của chuỗi ban đầu, m là độ dài của chuỗi mẫu cần tìm kiếm).
    • Trường hợp xấu nhất khi kí tự đầu tiên lặp lại liên tục trong chuỗi ban đầu. Khi đó, độ phức tạp của thuật toán là O(m*n).
    • Phù hợp cho các ứng dụng tìm kiếm chính xác như: số điện thoại, email, tên địa phương, tên người, ...
    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021