HABIT

#include 
#include 
#include 
#include 

using namespace std;

int getMostHabit(string &habit, int minLength);
int getCommonPrefixLength(string &s, int startIdx, int endIdx);
vector getSuffixArray(string &habit);

int main()
{
	int caseNum = 0;
	cin >> caseNum;

	int k = 0;
	string habit = "";

	for (int i = 0; i < caseNum; i++)
	{
		cin >> k;
		cin.ignore();

		std::getline(std::cin, habit);

		// Process
		int most = getMostHabit(habit, k);

		cout << most << endl;
	}
}

typedef struct Comparator {
	vector group;
	int t;

	Comparator(vector _group, int _t) {
		group = _group;
		t = _t;
	}

	bool operator() (int a, int b) {
		if (group[a] != group[b])  return group[a] < group[b];
		else return group[a + t] < group[b + t];
	}

}Comparator;

int getMostHabit(string &habit, int minLength)
{
	vector suffixArray = getSuffixArray(habit);

	int n = habit.size();

	int ret = 0;
	for (int i = 0; i < n - minLength; i++)
		ret = max(ret, getCommonPrefixLength(habit, suffixArray[i], suffixArray[i + minLength - 1]));

	return ret;
}

int getCommonPrefixLength(string &s, int startIdx, int endIdx)
{
	int i = startIdx, j = endIdx, k = 0;
	int n = s.size();

	while (i < n && j < n && s[i] == s[j]) { i++; j++; k++; }

	return k;
}

vector getSuffixArray(string &habit)
{
	int n = habit.size();

	int t = 1;
	vector group(n + 1);
	group[n] = -1;

	vector perm(n);

	for (int i = 0; i < n; i++)
	{
		group[i] = habit[i];
		perm[i] = i;
	}

	while (t < n)
	{
		Comparator compareUsingT2(group, t);

		sort(perm.begin(), perm.end(), compareUsingT2);

		/*cout << "						[ PERMISSION START ]						" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << "(group # " << group[perm[i]] << ") " << habit.substr(perm[i]) << endl;
		}
		cout << "						[ PERMISSION END ]							" << endl;
		cout << endl;*/

		vector new_group(n + 1);
		new_group[n] = -1;
		new_group[perm[0]] = 0;

		t *= 2;
		if (t >= n) break;

		for (int i = 1; i < n; i++)
		{
			if (compareUsingT2(perm[i - 1], perm[i]))
			{
				new_group[perm[i]] = new_group[perm[i - 1]] + 1;
			}
			else
			{
				new_group[perm[i]] = new_group[perm[i - 1]];
			}
		}

		group = new_group;
	}

	return perm;
}

 

HabitInput.txt

0.00MB

 

HabitOutput.txt

0.00MB

 

접미사 배열을 구하는 알고리즘 역시 이해하는데 쉽지 않았다. 이 때 쓰인 알고리즘은 맥스-마이버스 알고리즘이다.

접미사 배열을 구한 후, 이 배열을 이용해 K 개의 연속된 commonPrefix를 구하였고,

이렇게 구해진 commonPrefix들 중 길이가 가장 긴 값을 리턴하였다.