SPOJ.COM - Thuật toán bài BROKEN - Broken Keyboard

Đề bài:

Bàn phím của Bruce Force bị hỏng, chỉ một vài phím là vẫn còn hoạt động. Bruce đã nhận ra rằng anh ấy vẫn có thể viết chữ bằng việc thay đổi cách bố trí của các phím mỗi khi anh ấy cần nhập chữ cái mà hiện tại nó không thuộc m chữ cái còn hoạt động.

Bạn được đưa cho một dòng chữ mà Bruce muốn gõ. Và anh ấy yêu cầu bạn để nói cho anh ấy biết số lượng tối đa của những kí tự liên tiếp trong dòng chữ mà có thể được gõ mà không phải thay đổi cách bố trí của các kí tự trên bàn phím. Để đơn giản, chúng ta giả sử rằng mỗi phím trên bàn phím chỉ đại diện cho một chữ cái và không thể gõ chữ cái khác bằng việc gõ tổ hợp phím. Điều này có nghĩa là Bruce muốn biết độ dài lớn nhất của xâu con của dòng chữ cho ban đầu - cái mà bao gồm tối đa m kí tự khác nhau.

Đầu vào

Bao gồm nhiều test case, mỗi test case bao gồm 2 dòng. Dòng đầu tiên bao gồm số nguyên m (1 ≤ m ≤ 128), xác định số phím trên bàn phím còn hoạt động. Dòng thứ 2 của mỗi test case chứa dòng chữ mà Bruce muốn gõ. Giả sử rằng độ dài của dòng chữ không vượt quá 1000000 kí tự. Chú ý rằng dòng chữ đầu vào có thể chứa nhiều dấu cách, và dấu cách được xử lí giống như những kí tự khác.

Test case cuối cùng theo sau bởi một dòng chứa số 0.

Đầu ra

Mỗi test case in ra trên một dòng độ dài lớn nhất cần tìm.

Ví dụ

Đầu vào:

5
This can't be solved by brute force.
1
Mississippi
0

Đầu ra:

7
2

Giải thích:

• Test case thứ nhất: xâu con thỏa mãn là: "by_bru" ('' biểu diễn dấu cách)
• Test case thứ hai: xâu con thỏa mãn là: "ss"

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/BROKEN/

Phân tích

• Mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán.

• Ở đây mình sẽ sử dụng 2 biến để đánh dấu vị trí bắt đầu và vị trí đang xét hiện tại. Xâu con đang xét chính là xâu con từ vị trí bắt đầu đến vị trí hiện tại. Và mình sẽ duyệt từ đầu cho đến cuối của dãy.

• Đồng thời mình sử dụng một mảng đếm số lượng các kí tự hiện tại. Từ đó mình tính được số kí tự khác nhau của xâu con. Trong quá trình duyệt mình sẽ tìm được xâu con có độ dài lớn nhất.

• Cụ thể mời bạn xem code phía dưới để hiểu rõ hơn về thuật toán tham lam của mình.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

char str[1000005];  // Lưu xâu đầu vào
int  cnt[1000];     // Mảng đếm tần suất xuất hiện của kí tự

int main()
{
	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);

	int m = -1, length = 0;
	char gar;
	while(true)
	{
		// Nhập đầu vào và tính độ dài của xâu
		cin >> m;
		if (m == 0) break;
		gar = cin.get();

		length = 0;
		cin.getline(str, 1000005);
		while(str[length] != '\0') length++;

		for(int i=0; i<1000;i++)
			cnt[i] = 0;

		//////////////////////////
		int _max = 0;			// Độ dài xâu con lớn nhất thỏa mãn
		int start = 0;			// chỉ số bắt đầu
		int id = 0;				// chỉ số hiện tại
		int numDiffChar = 0;	// số kí tự khác nhau từ chỉ số bắt đầu đến chỉ số hiện tại

		// Duyệt từ đầu đến cuối xâu
		while(id < length)
		{
			// Giá trị mảng đếm = 0 nghĩa là kí tự đó chưa tồn tại
			if(cnt[str[id]] == 0)
			{
				// Nếu số kí tự khác nhau nhỏ hơn m thì ta sẽ cho kí tự đó vào xâu con
				// đồng thời tăng giá trị biến đếm số lần xuất hiện của kí tự, số kí tự khác nhau
				// và chỉ số hiện tại
				if(numDiffChar < m)
				{
					cnt[str[id]] = 1;
					numDiffChar++;
					id++;
				}
				else if(numDiffChar == m)
				{
					// Nếu số kí tự khác nhau đã bằng m rồi
					// thì ta không thể thêm kí tự mới vào, khi đó số kí tự khác nhau sẽ là m + 1
					// Do đó tôi phải dịch chỉ số bắt đầu lên cho đến khi số kí tự khác nhau < m
					// Lúc đó mới có thể thêm kí tự mới.
					int t = id - start;
					if(t > _max) _max = t;

					while(numDiffChar == m)
					{
						cnt[str[start]]--;
						if(cnt[str[start]] == 0) numDiffChar--;
						start++;
					}
				}
			}
			else
			{
				// Trường hợp kí tự đó đã xuất hiện trong xâu con rồi
				// thì tôi chỉ cần biến đếm số lần xuất hiện của kí tự đó.
				cnt[str[id]]++;
				id++;
			}
		}

		int t = id - start;
		if(t > _max) _max = t;
		cout << _max << endl;
	}
	return 0;
}