Алгоритм поиска максимальной встречаемости подстроки

Я могу построить дерево для решения этой конкретной проблемы.

Есть условный корневой узел. Первый персонаж - это первый ребенок. Второй символ является потомком первого символа a -> s в вашем случае. Он также начинает новый лист корневого узла. Если при добавлении узла вы посещаете существующий узел, вы увеличиваете его счетчик (начальное значение 1).

После этого вы посещаете каждый узел дерева, чтобы найти тот, у которого наибольшее количество на самом глубоком уровне (потому что, если "asdf" встречается 5 раз, то "a", "as" и "asd" встречаются минимум 5 раз, по определению).

Подстрока, которая повторяет больше всего будут, будет одной буквой, поэтому вы найдете букву, которая встречается чаще всего. Это довольно просто:

>>> str = 'Can Berk Güder'
>>> letters = [l for l in str]
>>> uniq_letters = set(letters)
>>> counts = [(letters.count(l), l) for l in uniq_letters]
>>> counts
[(1, 'B'), (1, 'C'), (1, 'G'), (1, 'a'), (1, 'd'), (1, 'k'), (1, 'n'), (1, 'ü'), (2, ' '), (2, 'e'), (2, 'r')]

// C# code, finds one of the most occurred non-empty substrings in O(n), proof by the reader!
int[] x = new int[65536];
foreach (char c in myString)
     x[(int)c]++;
int max = 0;
for (int i = 0; i < x.Length; ++i)
    if (x[max] < x[i])
        max = i;
return ((char)max).ToString();

Однако, вероятно, это не то, что вам нужно. Возможно, вам придется взглянуть на что-то вроде кодирования Хаффмана ...

Похоже, вы ищете что-то близкое к алгоритму сжатия. Сжатие работает путем поиска избыточной (повторяющейся) информации и замены ее указателем на первое вхождение. Вот несколько примеров кода для этого:

http://www.developerfusion.com/code/1642/string-compression/

http://www.howtodothings.com/computers/a1223-simple-string-compression.html

В строках длиной N

   No Of "1" character will be "N" which requires comparision of N * (N-1) / 2

   No of "2" characters will be "N-1" which requires comparision of (N-1) * (N-2) / 2


   No of "3" characters will be "N-2"  which requires comparision of (N-2) * (N-3) / 2

.............

и ни один из "N" символов не будет "1", что требует сравнения (1 * 0/2)

Следовательно, No Of Max Substrings = "N" + "N-1" + .... "1" = (N * (N + 1) / 2), и требуется сравнение (N + 1) * (N) * ( П-1) / 6

Если вы выполняете размещение сегмента (не сортировку) на каждом из символов одинакового размера, тогда

   No Of "1" character will be "N" which requires comparision of N -1 with buckets of N

   No of "2" characters will be "N-1" which requires comparision of (N-2) with Buckets of N-1

   No of "3" characters will be "N-2"  which requires comparision of (N-3) with Buckets of N-2

.............

и ни один из "N" символов не будет "1", что требует сравнения 0 с сегментом 1

Здесь он уменьшает общее количество сравнений до "N * (N-1) / 2"

Наконец, после того, как вы разместите ведро, возьмите ведро с наибольшим номером для вашего ответа.