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

Question

[Chvalov]

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

Пробелы так-же должны учитываться.

К примеру есть текст:

Сайт toster, бла бла бла Сайт toster

На выходе я должен получить:

Сайт toster

Еще пример сюда же:

aboibooolsabbooolsadf

На выходе:

booolsa

Что то я в тупике, в другом случае я бы завел массив со словами (разделитель слов пробел " "), нашел бы слова которые повторяются более одного раза и выбрал бы то слово которое длинее всех.
А вот как здесь поступить не знаю :(

Answer 1

[Александр Дорофеев]

Решение:

Класс LongestSubstringFinder, производящий эту операцию:

import java.util.Arrays;

public final class LongestSubstringFinder {

    private LongestSubstringFinder() {}

    public static String findLongestSubstringAtString(String string) {

        string = string.replaceAll("\\s+", " ");

        int quantityOfSuffixes = string.length();
        String[] suffixes = new String[quantityOfSuffixes];

        for (int i = 0; i < quantityOfSuffixes; i++) {
            suffixes[i] = string.substring(i, quantityOfSuffixes);
        }

        Arrays.sort(suffixes);

        String longestRepeatedSubstring = "";
        for (int i = 0; i < quantityOfSuffixes - 1; i++) {
            String x = findLongestCommonPrefixOfTwoStrings(suffixes[i], suffixes[i + 1]);

            if (x.length() > longestRepeatedSubstring.length()) {
                longestRepeatedSubstring = x;
            }
        }
        return longestRepeatedSubstring;
    }

    private static String findLongestCommonPrefixOfTwoStrings(String first, String second) {
        int quantity = Math.min(first.length(), second.length());
        for (int i = 0; i < quantity; i++) {
            if (first.charAt(i) != second.charAt(i))
                return first.substring(0, i);
        }
        return first.substring(0, quantity);
    }
}

Тесты(пройдены):

@Test
    public void testFindLongestSubstringAtStringFirst() throws Exception {
        String testString = "Сайт toster, бла бла бла Сайт toster";
        String neededResult = "Сайт toster";
        String longestSubstring = LongestSubstringFinder
                .findLongestSubstringAtString(testString);
        assertEquals(longestSubstring, neededResult);
    }

    @Test
    public void testFindLongestSubstringAtStringSecond() throws Exception {
        String testString = "aboibooolsabbooolsadf";
        String neededResult = "booolsa";
        String longestSubstring = LongestSubstringFinder
                .findLongestSubstringAtString(testString);
        assertEquals(longestSubstring, neededResult);
    }

Об алгоритме: здесь и здесь.

Comments

[Chvalov]

Спасибо большое

Answer 2

[aslan7470]

Идея:
Берем N последовательностей длины 1, начинающиеся в элементах 0..N-1, выписываем в массив позицию их 1го символа (0..N-1), сортируем по символу в этой позиции. Для групп с одинаковым символом вызываем рекурсивно, рассматривая 2й символ с позиции, записанной в массиве итд

Псевдокод:

find(N,A[])
  p[N]={0..N-1} // позиции начала подстрок
  l=0,ml=0,s // длина, макс длина подстроки, позиция подстроки макс длины
  finda(0,N)

// искать среди позиций p[i..j-1]  
def finda(i,j)
  if l>ml && j-i>1
    ml=l
    s=p[i]
  ++l
  // оставим в p[i..j-1] позиции <= N-l
  m=j,k=j=i
  while k<m
    if p[k]<=N-l
      p[j++]=p[k]
    ++k
  sort p[i..j-1]):A[p[i]+l]
  k=m=i
  while ++k<j
    if(A[p[k]+l]!=A[p[k-1]+l]) // конец группы подстрок с равным символом на позиции l от начала
      finda(m,k)
      m=k
  finda(m,j) // последняя группа подстрок с равным символом на позиции l от начала
  --l