SPOJ.COM - Thuật toán bài FINDSR - Find String Roots

Đề bài:

Trong toán học, căn bậc N của M là một số K thỏa mãn K^N = M hay KKK...K = M, trong đó có N số K nhân với nhau. Chúng ta có thể chuyển đổi chúng sang áp dụng với xâu. Trong bài toán này, chúng ta sẽ sử dụng ghép xâu thay vì phép nhân. Do đó, căn bậc N của xâu S là một xâu T thỏa mãn T^N = S, trong đó T^N = T.T.T.T...T là N xâu T ghép với nhau. Ví dụ nếu xâu S là "abcabcabcabc", với N = 2 thì xâu T = "abcabc" là căn bậc N của S. Và nếu N = 4 thì xâu T = "abc". Chú ý rằng nếu N = 1 thì căn bậc N của S là chính nó.

Cho trước một xâu S và bạn phải tìm ra số N lớn nhất mà căn bậc N của S tồn tại. Trong ví dụ trên đáp án là N = 4, bởi vì không có số nguyên N nào lớn hơn 4 mà tồn tại căn bặc N của S.

Đầu vào

Đầu vào bao gồm nhiều test case, mỗi cái được cho trên một dòng. Mỗi dòng không tồn tại xâu rỗng và có tối đa 10⁵ kí tự, và chỉ bao gồm chữ số và chữ cái thường. Dòng cuối cùng chứa một kí tự '*' (không bao gồm '').

Đầu ra

Với mỗi test case, in ra số nguyên duy nhất là kết quả.

Ví dụ

Đầu vào:

abcabcabcabc
abcdefgh012
aaaaaaaaaa
*

Đầu ra:

4
1
10

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

Phân tích

• Ở đây yêu cầu là tìm ra số N lớn nhất mà tồn tại căn bậc N của S, nghĩa là độ dài mỗi xâu T phải là nhỏ nhất. Do đó, mình sẽ xét độ dài của T từ 1 rồi tăng dần lên. Khi nào thỏa mãn thì mình sẽ dừng lại và đó chính là kết quả cần tìm.

• Sau đây, mời bạn theo dõi cách triển khai code sử dụng thuật toán tham lam Greedy 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;

const int MAX = 1000000;

/**
* Tính độ dài xâu str
*/
int GetLength(char *str)
{
	int length = 0;
	while(str[length] != '\0') length++;
	return length;
}

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

	char str[MAX];
	while(true)
	{
		cin >> str;
		int length = GetLength(str);
		if(length == 1 && str[0] == '*') break;

		int len_sub = 1;	// Độ dài xâu con T
		int N = 0;
		while(true)
		{
			// Duyệt từng độ dài của len_sub và tăng dần lên
			if(length % len_sub != 0)
			{
				len_sub++;
				continue;
			}

			// Kiểm tra xem với độ dài len_sub như vậy có thỏa mãn hay không
			int id = 0;
			bool check = true;
			while(true)
			{
				if(id + len_sub + 1> length) break;
				for(int i = 0; i < len_sub; i++)
				{
					if(str[i+id] != str[i+len_sub+id])
					{
						check = false;
						break;
					}
				}
				if(check == false) break;
				id += len_sub;
			}

			if(check == true)
			{
				N = length / len_sub;
				break;
			}
			len_sub++;
		}
		cout << N << endl;
	}
	return 0;
}