алгоритм нахождения максимального вхождения подстроки

Question

Учитывая строку S, каков наилучший алгоритм для поиска подстроки, которая повторяется максимальное количество раз.

Например, в "assdssfssd" это "ss", которое повторяется максимальное количество раз.

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

>>> 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')]

Answer 4

В длинных струнах "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 ) * (N-1) / 6

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

   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»

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

Answer 5

// 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();

Это, вероятно, не то, что вы хотите, хотя. Возможно, вам придется посмотреть на что-то вроде кодирования Хаффмана ...