Góp ý thuật toán: Tô màu những từ được nhập trong 1 chuỗi cho trước

#1

Xin chào mọi người. Nhờ mọi người giúp em bài tập sau a!

Đề bài: Cho 1 chuỗi mẹ, sau đó cho người dùng nhập vào chuỗi con rồi in đậm trong chuỗi mẹ những từ (chuỗi con) có trong chuỗi mẹ.

VD: Chuỗi mẹ:
" Vâng, hôm nay, tại đây, các bạn sẽ chứng kiến 1 sự khởi đầu cho 1 xu hướng mới của thế giới công nghệ trên toàn cầu, không thể tin nổi, thật không thể tin nổi, không thể tin nổi, chính chúng tôi cũng không thể tin nổi khi mình làm được như vầy, thật không thể tin nổi, không thể tin nổi "

Chuỗi con: " không thể tin nổi "

=> Xuất ra màn hình:
" Vâng, hôm nay, tại đây, các bạn sẽ chứng kiến 1 sự khởi đầu cho 1 xu hướng mới của thế giới công nghệ trên toàn cầu, không thể tin nổi, thật không thể tin nổi, không thể tin nổi, chính chúng tôi cũng không thể tin nổi khi mình làm được như vầy, thật không thể tin nổi, không thể tin nổi "

Source code:

void textcolor(int x)
{
	HANDLE mau;
	mau = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(mau, x);
}
void Strstr(const char *s1, const char *s2)
{
	int arr[100], idx = 0;
	int length_s = Strlen(s1), length_key = Strlen(s2);
	for (int i = 0; i < length_s; i++)
	{
		if (s1[i] == s2[0])
		{
			int k = 1;
			int Check = true;
			int temp = i + 1;
			for (int j = 1; j < length_key; j++)
			{
				if (s1[temp++] != s2[j])
				{
					Check = false;
					break;
				}
			}
			if (Check == true)
			{
				arr[idx++] = i;
			}
		}
	}
	idx = 0;
	for (int i = 0; i < length_s; i++)
	{
		if (i == arr[idx])
		{
			textcolor(14);
		}
		if (i == arr[idx] + length_key)
		{
			textcolor(7);
			idx++;
		}
		printf("%c", s1[i]);
	}
 
}
int main()
{
	char s1[] = "Vang, hom nay, tai day, cac ban se chung kien 1 su khoi dau cho 1 xu huong moi cua the gioi cong nghe tren toan cau, khong the tin noi, that khong the tin noi, khong the tin noi, chinh chung toi cung khong the tin noi khi minh lam duoc nhu vay, that khong the tin noi, khong the tin noi";
	char *s2 = "khong the tin noi";
	Strstr(s1, s2);
	
	getch();
	return 0;
}

Mọi người có ai có thể rút gọn / tối ưu thuật toán trên giùm em được không ạ, chứ thấy nó dài dòng quá mà không biết có đúng hết mọi trường hợp không, xin cảm ơn !

1 Like
#2

bạn có thể dùng hàm strtok để tách các từ từ chuỗi mẹ và chuỗi con ra và lưu lại trong một mảng hay vector nào đó. Sau đó dùng vòng lặp kiểm tra, mình nghĩ code sẽ ngắn hơn và độ phức tạp thuật toán cũng giảm xuống O(n).

1 Like
#3

Mình chưa biết vector :slight_smile: và mình cũng đang cố gắng giảm thiểu sự “nhờ vả” vào hàm có sẵn ngoại trừ những hàm bắt buộc như strlen, strdup.

1 Like
#4

không biết vector cũng chẳng sao, nó chỉ là một mảng được cấp phát động mà thôi, bạn cũng có thể thay bằng một mảng các string đc cấp phát động hoặc tĩnh tùy bạn, điều nay không quá quan trọng. hàm strtok là 1 hàm trong thư viện chuẩn string.h bạn không dùng thì dùng cái gì :3
Mình nghĩ bạn không nên nghĩ như vậy, bạn cần phải thành thạo càng nhiều càng tốt các hàm được xây dựng trong thư viện chuẩn và sử dụng nó 1 cách linh hoạt. Còn nếu không muốn dùng từ đó thì bạn hoàn toàn có thể viết lại các hàm này :3 đơn giản mà ^^

2 Likes
#5

Bạn thử tìm hiểu matching algorithm. Đặc biệt là Knuth-Morris-Pratt (KMP) hoặc Rabin-Karp (hash).

1 Like
#6

OK, cảm ơn bạn nhé

Mình tự viết :slight_smile:

Mình định úp các hàm xử lý chuỗi do chính tay mình tạo ra - giống hệt các hàm hổ trợ có sẵn nhưng sợ bị nói là rảnh

Thanks anh :slight_smile:

#7

Viết lại các hàm trong thư viện chuẩn là 1 cách học rèn luyện kỹ thuật lập trình rất tốt, không ai nói bạn rãnh đâu haha chúc may mắn ^^

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?