Trong một thời gian dài tôi băn khoăn không hiểu cái gì có thể cực đắt, cực hiện đại, có thể cực kì vô dụng. Và rồi tôi phát hiện ra máy tính là một cái máy ngu ngốc có khả năng làm những việc thông minh phi thường, trong khi lập trình viên là những người thông minh có khả năng làm những việc ngu ngốc phi thường. Bill Bryson
STDIO 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.
Nội dung bài viết

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ạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG