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

Posted on December 4th, 2016

Đề bài:

Trong toán học, căn bậc N của M là một số K thỏa mãn KN = 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 TN = S, trong đó TN = 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 10kí 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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!