STDIO
Tìm kiếm gần đây

    Nội dung

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

    Trong những giải thuật tìm kiếm đa số đều sử dụng nhiều cho các mảng có các phần tử là số. Trong bài viết này và một số bài viết sau, tôi sẽ giới thiệu thêm về các giải thuật tìm kiếm một chuỗi kí tự trong một đoạn văn bản.

    Giới thiệu

    Trong các bài viết trước tôi đã đề cập đến một số giải thuật tìm kiếm. Tuy nhiên, những giải thuật trên đều sử dụng nhiều cho các mảng có các phần tử là số. Trong bài viết này và một số bài viết sau, tôi sẽ giới thiệu thêm về các giải thuật tìm kiếm một chuỗi kí tự trong một đoạn văn bản. Trong phạm vi bài viết này, tôi sẽ trình bày về giải thuật Naive String Search.

    Naive String Search

    Ý tưởng

    Ứng dụng thuật toán tìm kiếm tuần tự trên chuỗi. Nói cách khác, ta lần lượt xét từng vị trí t_index trong chuỗi kí tự gốc target từ 0 đến t_size – p_size, so sánh target[t_index…(t_index + p_index)] với chuỗi kí tự mẫu tìm kiếm pattern[p_index…p_size] bằng cách xét từng cặp kí tự một và đưa ra kết quả tìm kiếm.

    ss_1

    Các bước thực hiện

    Bước 1: t_index = 0.

    Bước 2

    • Bước 2.0: p_index = 0.
    • Bước 2.1: Thực hiện so sánh target[t_index + p_index]  và pattern[p_index]. Nếu target[t_index + p_index] != pattern[p_index], thì dừng vòng lặp và chuyển đến bước 3.
    • Bước 2.2: Nếu p_index < p_size lặp lại bước 2.1 với ++p_index . Ngược lại thì dừng vòng lặp.
    • Bước 2.3: Nếu p_index == p_size -1 thì lưu lại vị trí t_index.

    Bước 3: Nếu t_index < t_size – p_size thì quay lại bước 2 với ++t_index. Ngược lại thì dừng.

    Hiện thực

    int* NaiveStringSearch(char* target, char* pattern)
    {
    	int	t_size		= strlen(target);
    	int	p_size		= strlen(pattern);
    	int*p_result	= new int[t_size / p_size];
    	int	r_index		= 0;
     
    	for (int t_index = 0; t_index < t_size - p_size; ++t_index)
    	{
    		for (int p_index = 0; p_index < p_size; ++p_index)
    		{
    			if (target[t_index + p_index] != pattern[p_index])
    				break;
     
    			if (p_index == p_size - 1)
    			{
    				p_result[r_index] = t_index;
    				r_index++;
    			}
    		}
    	}
     
    	return p_result;
    }

    Đá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).

    Bài viết liên quan

    Linear Search - Tìm Kiếm Tuyến Tính

    Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất: ...

    Trương Diễm Hương15/08/2015

    Tìm Hiểu Về Strings Trong Python

    Trong bài viết Biến Và Kiểu Dữ Liệu lần trước tôi đã giới thiệu một số kiểu dữ liệu chuẩn trong Python. Tiếp tục cho chuỗi bài viết về chương trình hướng dẫn ngôn ngữ ...

    Ryan Lê20/03/2015

    Thuật toán Breadth First Search

    Thuật toán Breadth First Search (Tìm kiếm theo chiều rộng) cùng với Thuật toán Depth First Search là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí tuệ nhân ...

    Trần Minh Thắng19/09/2015

    Thuật toán Depth First Search

    Thuật toán Depth First Search - DFS (tìm kiếm theo chiều sâu) cùng với Thuật toán Breadth First Search - BFS là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí ...

    Trần Minh Thắng19/09/2015

    String Trong Java

    Kiểu String trong Java là một trong những kiểu dữ liệu quan trọng. Bài viết giới thiệu về String trong Java và các thao tác trên chúng.

    Lê Minh Trung06/05/2015

    Phần 1 - Cây Nhị Phân Tìm Kiếm

    Các thao tác trên cây nhị phân tìm kiếm - khởi tạo, chèn, tìm kiếm, duyệt cây với C/C++.

    Nguyễn Đăng Khánh01/02/2016

    Học SEO Trong 1 Ngày - Phần 2

    Phân tích keyword thủ công để nâng cao khả năng chủ động trong việc tìm ra keyword hiệu quả nâng cao chất lượng website trên công cụ tìm kiếm.

    STDIO Solutions11/07/2020

    Biến Và Kiểu Dữ Liệu Trong PHP

    Biến là một khái niệm quen thuộc trong bất kì ngôn ngữ lập trình nào. Tuy nhiên ở mỗi ngppn ngữ, cách khai báo biến và kiễu dữ liệu ngôn ngữ hỗ ...

    Nguyễn Thị Trúc Linh20/02/2017

    Học SEO Trong 1 Ngày - Phần 1

    Hiểu biết về cách hoạt động của Google, keyword và các công cụ hỗ trợ phân tích keyword, các khái niệm về keyword trong SEO.

    STDIO Solutions11/07/2020

    Thư Viện Xử Lý Chuỗi - std::string

    Lập trình với chuỗi là vấn đề mà bất cứ lập trình viên nào cũng trải qua. Với mức độ trừu tượng hóa cao, C++ đã hỗ trợ thêm cho chúng ta thư viện std::string dành riêng ...

    Trương Diễm Hương15/08/2015

    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
    [email protected]

    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 - 2020