Должны помочь суффиксные структуры: суффиксный массив/дерево/автомат. Например, с точки зрения дерева надо всего лишь посмотреть все его вершины (а их линия) и для каждой уметь быстро понимать, сколько раз соответствующая подстрока встречается в строке (это делается простым предподсчётом).

Мне они кажутся довольно сложной темой (в порядке сложности: массив, автомат, дерево). К сожалению, с ходу не могу привести ссылки, где хорошо описано.

Будем тернарным поиском перебирать длину ответа. На каждой итерации нам нужно будет уметь узнавать максимальное число вхождений по всем подстрокам длины X. Это можно узнать за O(NlogN), используя хеши. Эта величина — максимальное число вхождений по всем подстрокам длины X, монотонно убывает с увеличением Х. Х, собственно, монотонно возрастает с увеличением Х. Тогда функция f(X) = Х *  < максимальное число вхождений по всем подстрокам длины Х >  удовлетворяет условиям тернарного поиска.

Это правда или нет?

1. Строим суффиксный массив за O(n*log(n))
2. Из него строим массив LCP за O(n) реализация
3. Дальше "задачка на стек":

Stack<w,id,h> stack
maxH = n
maxW = 1
start = 0

// LCP[n - 1] = 0

for (int i = 0; i < n; i++) {
	x = 1
	while(!stack.isEmpty() && lcp[i] <= stack.peek().h) {
		w,id,h = stack.pop()	
		x += w
		if (x * h > maxW * maxH) {
			maxW = x;
			maxH = h;
			start = suffArray[id];
		}		
	}
	if (stack.isEmpty() || lcp[i] > stack.peek().h) {
		stack.push(< x, i , lcp[i] >);				
	}
}

// Ответ это подмассив данного массива [start, start + maxH)

Решение суффиксным автоматом: code Идея: аналогично поиску количества вхождений подстроки в тексте(посмотреть можно на e-maxx.ru) найдем для каждого состояния v размер множества endpos(v), теперь собственно найдем то состояние, для которого искомая величина максимальна. Теперь осталось найти соответствующую подстроку, я это делал так, найдем для каждого состояния, можно ли по суффиксным ссылкам достигнуть искомое состояние(это делается ленивой динамикой, например). А потом просто шел по строке и переходил по символам, и как только попадал в состояние, из которого достижимо искомое состояние, выводил последние len(v) символов. Со слов может непонятно)) Надеюсь код исправит все непонятности.

зы. Теперь вопрос от меня сообществу, можно ли находить подстроку максимальной длины соответствующую определенному состоянию умнее, чем это делал я, а то мне кажется, что какой-то костыль придумал=)

ADD: Господа минусующие, вы хотя бы свои комменты давали по этому поводу. Код работает, причем асимптотически оптимально. Что не так?