PKU 3261 Milk Patterns

• 最長部分繰り返し文字列という問題だと思います
• Spaghetti Sourceのライブラリをお借りしました

#define SETNUM(rank, i,s) \
	NUM[i] = make_pair(make_pair(rank[i], i+s<n?rank[i+s]:n), i);
#define RENUMBER(rank) \
	sort(NUM.begin(), NUM.begin()+n); \
	rank[ NUM[0].second ] = 0; \
	for (int i = 1; i < n; ++i) \
	rank[ NUM[i].second ] = rank[ NUM[i-1].second ] \
	+ (NUM[i-1].first != NUM[i].first) ;

int ranks[32][200000];
void karp_miller_rosenberg_pre(const vector<int>& text) {
	const int n = text.size();
	int m = 0;
	vector<pair<pair<int,int>,int> > NUM(n);
	copy(text.begin(), text.begin()+n, ranks[m]);
	for (int k = 0; k <= n; k ? k*=2 : ++k) { // power of 2
		for (int i = 0; i < n; ++i) SETNUM(ranks[m], i, k);
		if (k > 0) ++m; RENUMBER(ranks[m]);
	}
}
int repeated_factor(const vector<int>& text, int r, int k) {
	const int n = text.size();
	int t, s;
	vector<pair<pair<int,int>,int> > NUM(n);
	vector<int> rank(n);
	for (s = 1, t = 0; s * 2 < r; s *= 2, ++t);
	for (int i = 0; i < n; ++i) SETNUM(ranks[t], i, r-s);
	RENUMBER(rank);
	vector<int> count(n);
	for (int i = 0; i < n; ++i)
		if (++count[ rank[i] ] >= k) return i;
	return -1;
}
vector<int> longest_repeated_factor(const vector<int>& text, int k) {
	karp_miller_rosenberg_pre(text);
	int low = 1, high = text.size();
	while (low+1 < high) {
		int mid = (low + high) / 2;
		if (repeated_factor(text, mid, k) < 0) high = mid;
		else                                    low = mid;
	}
	int t = repeated_factor(text, low, k);
	return t >= 0 ? vector<int>(text.begin()+t, text.begin()+t+low) : vector<int>();
}

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int> text;
	for (int i = 0; i < N; ++i) {
		int in;
		cin >> in;
		text.push_back(in);
	}

	const vector<int> answer = longest_repeated_factor(text, K);
	//for (vector<int>::const_iterator it = answer.begin(); it != answer.end(); ++it) {
	//	cout << *it << " ";
	//}
	//cout << endl;
	cout << answer.size() << endl;
}

Spaghetti Source - 最長繰り返し部分文字列 (Karp Miller Rosenberg) - http://www.prefield.com/algorithm/string/karp_miller_rosenberg.html