Самая длинная повторяющаяся последовательность байтов

Question

У меня есть код, который должен искать самую длинную повторяющуюся последовательность. Но в этой последовательности

7888885466662716666

и выводит первое вхождение в индексе 1-5, а второе в 2-6, элемент 8. Но 6 должно быть выведено, так как они дублируются. Я думал, чтобы пройти мою последовательность этого алгоритма по этому пути

• проверить, повторяется ли первый символ по всей строке, если не

• проверить, повторяются ли все 2 начальных символа, если нет

• проверить, если 3 ...

Но я не знаю, как включить это в мой код, вы можете сказать?

    private int element;
    private int lastElement;
    private int length;

    private byte[] readByteFromFile(File name) throws IOException {
        return Files.readAllBytes(name.toPath());
    }

    private void searchByte(byte[] byteMass) throws InterruptedException {
        for (int i = 0; i < byteMass.length; i++) {
                int count = 0;
                for (int j = i + 1; j < byteMass.length; j++) {
                    if (byteMass[i + count] == byteMass[j]) {
                        if (count >= length) {
                            length = count + 1;
                            element = i;
                            lastElement = j - count;
                        }
                        count++;
                    } else {
                        count = 0;
                    }
                }
        }
    }

Answer 1

Вот мое взломанное вместе решение, которое я написал вчера ...

В основном он проверяет, является ли input.charAt(i) == input.charAt(i + 1) и, если да, запускает второй цикл, пока они не совпадают, все время добавляя к String, и добавляет к List. И повтори.

Затем проверьте List для самого высокого случая (бессовестно украденный у здесь )

public static void addToList(String input) {
    String temp;
    List<String> l = new ArrayList<>();
    for (int i = 0; i < input.length() - 1; i++) {
        if (input.charAt(i) == input.charAt(i + 1)) {
            temp = String.valueOf(input.charAt(i));
            for (int j = i; j < input.length() - 1; j++) {
                if (input.charAt(j) == input.charAt(j + 1)) {
                    temp += String.valueOf(input.charAt(j + 1));
                    if (j == input.length() - 2) {
                        i = j;
                        if (!temp.isEmpty()) {
                            l.add(temp);
                        }
                        break;
                    }
                } else {
                    i = j - 1;
                    if (!temp.isEmpty()) {
                        l.add(temp);
                    }
                    break;
                }
            }
        }
    }
    System.out.println(getHighestOccurences(l));
}

public static String getHighestOccurences(List<String> list) {
    int max = 0;
    int curr;
    String currKey = null;
    Set<String> unique = new HashSet<>(list);
    for (String key : unique) {
        curr = Collections.frequency(list, key);
        if (max < curr) {
            max = curr;
            currKey = key;
        }
    }
    return currKey;
}

Если ваш ввод String input = "7888885466662716666"; и вызов addToList(input);, то вы получите:

6666

.

Демонстрация в Интернете

Answer 2

Я буду совершенно честен, я не слишком горжусь этим решением. В некоторых других языках программирования, в которых я достаточно опытен, я мог бы получить решение довольно легко ( вот возможная реализация в 05AB1E например ), но в Java это очень сложно imho.

Мне удалось найти решение путем преобразования ввода byte[] в String и проверки его подстрок. Однако с точки зрения производительности это дерьмо, поэтому я бы посоветовал продолжить поиск альтернативного способа сделать это.

Несмотря на это, мой код работает, поэтому я все равно опубликую его, если его части будут полезны или вдохновляющими:

class Main{
  public static void main(String[] args){
    Main m = new Main();
    m.test("7888885466662716666".getBytes());
  }

  private void test(byte[] input){
    String result = findLongestRepeatedSubsequence("7888885466662716666".getBytes());
    System.out.println("The longest repeating subsequence in " + new String(input) + " is: " + result);
  }

  private String findLongestRepeatedSubsequence(byte[] byteMass){
    // Convert the bytes to a String:
    String bytesAsString = new String(byteMass);
    // Loop as long as this String has at least 1 character left:
    while(bytesAsString.length() > 0){
      // Split the String into characters, where each character is a loose String of length 1
      String[] charsAsStringArray = bytesAsString.split("");
      int length = charsAsStringArray.length;
      int maxCount = 0;
      int startingIndex = 0;
      // Loop `i` in the range [0, length_of_String_array)
      for(int i = 0; i < length; i++){
        // Take the substring where the first `i` characters are removed
        String subString = bytesAsString.substring(i);
        String currentChar = charsAsStringArray[i];
        // Count the amount of subsequent times the current character occurs at the start of the substring
        int count = subString.length() - subString.replaceFirst(currentChar+"*", "").length();
        // If this count is larger than our current maxCount:
        if(count > maxCount){
          // Replace the maxCount with this count
          maxCount = count;
          // And set the index where we've found this longest subsequence (`i`) as well
          startingIndex = i;
        }
      }
      // After we've checked all substrings, get the longest subsequence we've found
      String longestSub = bytesAsString.substring(startingIndex, startingIndex + maxCount);
      // Split the entire String with this longest subsequence to get its occurrence-count
      int occurrenceCounter = bytesAsString.split(longestSub, -1).length - 1;
      // If we've found a subsequence that occurs at least twice:
      if(occurrenceCounter > 1){
        // Return it as result
        return longestSub;
      }
      // If this longest subsequence only occurs once:
      else{
        // Remove the first character of this found subsequence from the String
        bytesAsString = bytesAsString.substring(0, startingIndex) +
                        (startingIndex < length-1 ? 
                           bytesAsString.substring(startingIndex + 1)
                         :
                           "");
      }
    }
    // Mandatory return if the input is empty
    return null;
  }
}

Попробуйте онлайн. (ПОЛЕЗНО: содержит несколько дополнительных строк печати по сравнению с кодом выше.)