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 Target và Pattern.
    • 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.

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 target vì pattern 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, ...