Наиболее распространенная подстрока длины X

Это должно быть O (n * m), где m - средняя длина строки в списке. Для очень малых значений m алгоритм будет приближаться к O (n)

• Создайте хеш-таблицу счетчиков для каждой длины строки
• Выполните итерацию по вашей коллекции строк, обновляя хеш-таблицу соответственно, сохраняя текущее наиболее распространенное число как целочисленная переменная отдельно от хеш-таблицы
• сделано.

Я не вижу простого способа сделать это строго за время O (n), если только X не фиксирован и не может считаться константой. Если X является параметром алгоритма, то наиболее простой способ сделать это на самом деле будет O (n * X), ​​так как вам нужно будет выполнять операции сравнения, копии строк, хэши и т. Д. На подстроке длины X в на каждой итерации.

(Я на минуту представляю, что s - это многогигабайтная строка, а X - некоторое число больше миллиона, и не вижу никаких простых способов сравнения строк или хеширования подстрок length X, которые равны O (1) и не зависят от размера X)

Можно было бы избежать копирования строк во время сканирования, оставив все на месте, и избежать повторного хеширования всей подстроки - возможно, используя алгоритм инкрементного хеширования, где вы можете добавлять по байту за раз, и удалить самый старый байт - но я не знаю ни одного такого алгоритма, который не приводил бы к огромному количеству коллизий, которые нужно было бы отфильтровать с помощью дорогостоящего шага постобработки.

Обновление

Кейт Рэндалл указывает, что этот вид хеша известен как скользящий хеш . Тем не менее, по-прежнему остается, что вам придется сохранять начальную позицию строки для каждого совпадения в вашей хэш-таблице, а затем проверять после сканирования строки, что все ваши совпадения были истинными. Вам нужно будет отсортировать хеш-таблицу, которая может содержать nX записей, в зависимости от количества совпадений, найденных для каждого хеш-ключа, и проверить каждый результат - вероятно, это невозможно сделать за O (n).

Это приводит к огромному количеству коллизий, которые необходимо отфильтровать с помощью дорогостоящего шага постобработки.

Обновление

Кейт Рэндалл указывает, что этот вид хеша известен как скользящий хеш . Тем не менее, по-прежнему остается, что вам придется сохранять начальную позицию строки для каждого совпадения в вашей хэш-таблице, а затем проверять после сканирования строки, что все ваши совпадения были истинными. Вам нужно будет отсортировать хеш-таблицу, которая может содержать nX записей, в зависимости от количества совпадений, найденных для каждого хеш-ключа, и проверить каждый результат - вероятно, это невозможно сделать за O (n).

Это приводит к огромному количеству коллизий, которые необходимо отфильтровать с помощью дорогостоящего шага постобработки.

Обновление

Кейт Рэндалл указывает, что этот вид хеша известен как скользящий хеш . Тем не менее, по-прежнему остается, что вам придется сохранять начальную позицию строки для каждого совпадения в вашей хэш-таблице, а затем проверять после сканирования строки, что все ваши совпадения были истинными. Вам нужно будет отсортировать хеш-таблицу, которая может содержать nX записей, в зависимости от количества совпадений, найденных для каждого хеш-ключа, и проверить каждый результат - вероятно, это невозможно сделать за O (n).

что вам нужно будет сохранить начальную позицию строки для каждого совпадения в вашей хеш-таблице, а затем после сканирования строки убедиться, что все ваши совпадения были истинными. Вам нужно будет отсортировать хеш-таблицу, которая может содержать nX записей, в зависимости от количества совпадений, найденных для каждого хеш-ключа, и проверить каждый результат - вероятно, это невозможно сделать за O (n).

что вам нужно будет сохранить начальную позицию строки для каждого совпадения в вашей хеш-таблице, а затем после сканирования строки убедиться, что все ваши совпадения были истинными. Вам нужно будет отсортировать хеш-таблицу, которая может содержать nX записей, в зависимости от количества совпадений, найденных для каждого хеш-ключа, и проверить каждый результат - вероятно, это невозможно сделать за O (n).

Простое решение в Python

from collections import defaultdict
from operator    import itemgetter

def naive(s, X):
    freq = defaultdict(int)
    for i in range(len(s) - X + 1):
        freq[s[i:i+X]] += 1
    return max(freq.iteritems(), key=itemgetter(1))

print naive("aoaoa", 3)
# -> ('aoa', 2)

На простом английском

1. Создать отображение: подстрока длины X -> сколько раз это встречается в s строка

    для i в диапазоне (len (s) - X + 1):
    freq [s [i: i + X]] + = 1
   

2. Найдите в сопоставлении пару с самым большим вторым элементом (частотой)

    max (freq.iteritems (), key = itemgetter (1))
   

Алгоритм LZW делает это

Это именно то, что делает алгоритм сжатия Лемпеля-Зива-Велча (LZW, используемый в формате изображений GIF). Он находит распространенные повторяющиеся байты и заменяет их на что-то короткое.

LZW в Википедии

Вот версия, которую я сделал на C. Надеюсь, что это поможет.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char *string = NULL, *maxstring = NULL, *tmpstr = NULL, *tmpstr2 = NULL;
    unsigned int n = 0, i = 0, j = 0, matchcount = 0, maxcount = 0;

    string = "aoaoa";
    n = 3;

    for (i = 0; i <= (strlen(string) - n); i++) {
        tmpstr = (char *)malloc(n + 1);
        strncpy(tmpstr, string + i, n);
        *(tmpstr + (n + 1)) = '\0';
        for (j = 0; j <= (strlen(string) - n); j++) {
            tmpstr2 = (char *)malloc(n + 1);
            strncpy(tmpstr2, string + j, n);
            *(tmpstr2 + (n + 1)) = '\0';
            if (!strcmp(tmpstr, tmpstr2))
                matchcount++;
        }
        if (matchcount > maxcount) {
            maxstring = tmpstr;
            maxcount = matchcount;
        }
        matchcount = 0;
    }

    printf("max string: \"%s\", count: %d\n", maxstring, maxcount);

    free(tmpstr);
    free(tmpstr2);

    return 0;
}

Невозможно сделать это за O (n).

Не стесняйтесь голосовать против меня, если сможете доказать, что я ошибаюсь в этом, но у меня ничего нет.

Вы можете построить дерево подстрок. Идея состоит в том, чтобы организовать ваши подстроки как телефонную книгу. Затем вы просматриваете подстроку и увеличиваете ее количество на единицу.

В приведенном выше примере дерево будет иметь разделы (узлы), начинающиеся с букв: 'a' и 'o'. «a» появляется три раза, а «o» - дважды. Таким образом, эти узлы будут иметь счетчик 3 и 2 соответственно.

Затем под узлом «a» появится подузел «o», соответствующий подстроке «ao». Это появляется дважды. Под узлом 'o' дважды появляется 'a'.

Мы продолжаем таким образом, пока не дойдем до конца строки.

Представление дерева для 'abac' может быть таким (узлы на одном уровне разделяются запятой, подузлы находятся в скобках, счетчики появляются после двоеточия).

a: 2 (b: 1 (a: 1 (c: 1 ())), c: 1 ()), b: 1 (a: 1 (c: 1 ()) )), c: 1 ()

Если дерево вытянуть, это будет намного очевиднее! Все это, например, говорит о том, что строка 'aba' появляется один раз, или строка 'a' появляется дважды и т. Д. Но объем памяти значительно уменьшается и, что более важно, значительно ускоряется поиск (сравните это с сохранением списка под- строк).

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

Время работы, вероятно, примерно равно O (log (n)), не уверен, но определенно лучше, чем O (n ^ 2).