Как найти самую длинную подстроку в строке которая встречается ее менее 2 раз?

Question

[Никита]

Есть строка, как в ней найти подстроку, которая встречается не меньше 2х раз и является самой длинной из таких подстрок.

Готовое решение не прошу, не могу понять алгоритм поиска.

Comments

[Алексей Черемисин]

Как-то так (это не решение!) - https://stackoverflow.com/questions/32788407/find-...

[Никита]

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

[Орхан Гасанлы]

Никита, как по мне регулярка это выход. К тому же вам нужно задачу решить, а не заниматься оптимизацией)

[Никита]

Орхан Гасанлы, в том то и дело, что мне запретили использовать регулярки, так как не проходит по времени

[Орхан Гасанлы]

Никита, а ну так это другое дело.

[Алексей Черемисин]

Никита, Ну, тогда indexOf спасет отца русской демократии :-) - https://www.baeldung.com/java-indexOf-find-string-...

int found = 0;
    int index = 0;
    int len =0;
    while(index != -1){
        index = mystring.indexOf(word, index + len);
        if (index != -1) {
            found +=1;
        }
        len = word.length();
    }
    return found;

[Орхан Гасанлы]

Никита,
посмотрите сюда:
https://stackabuse.com/java-check-if-string-contai...
contains()
indexOf()

Answer 1

[Dmitry Roo]

1. Делим длину строки на 2 - получаем первый возможный вариант длины подстроки.
2. В цикле, потихоньку уменьшая длину подстроки, ищем
а. Возможные подстроки.
б. Частоту их появления в исходной строке (например, складывая в Map).

Пример:
Строка: aabcdaa
Шаг первый: возможная длина 7/2 -> три символа.
Шаг второй: выбираем строки по три символа -> aab, abc, bcd, daa -> нет повторений.
Шаг третий: выбираем строки по два символа -> aa, ab, bc, cd, aa -> нашлась строка aa - наиболее длинная, которая встречается 2 раза.

Comments

[Dmitry Roo]

Bavashi, точно должно. Я - не робот))

Answer 2

[Therapyx]

хм, тут зависит еще от вводных. Если не прибегать к определенным фишкам языков, а абстрагироваться тем, что есть почти везде, то я бы скорее всего делал так:
1) Сделал бы мэп, хешмэп и (co.) в виде "String, int", где стринг это будет часть разбитой подстроки, а инт - это каунтер
2) Брал бы подстроку и разбивал ее почастично, добавляя в эту структуру данных с инициальным каунтером 1, но
2.2) Добавляя делать проверку, есть ли такой паттерн уже в ней? если да, то увеличить каунтер
2.3) Если нету, то добавить в новый индекс с базовым каунтером.
3) в самом конце пробегаешься по структуре данных, где каунтер 2 и выше, вычисляя приэтом максимум из кол-ва символов в подстроках