Найдите самую длинную повторяющуюся последовательность - PullRequest
Новая
       11

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

0 голосов
/ 12 сентября 2018

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

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) {
    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;
            }
        }
    }
}

Предположим, что мой файл содержит такую ​​последовательность чисел:

444478126354444

В случае обработки мой метод выведет, что первое вхождение было в 0, а второе в 11 и длина последовательности = 4

Но если у меня есть такая последовательность

133333444478126354444

Тогда мой метод выведет, что первое вхождение было в 1, а второе в 2, и длина последовательности 4

Как это можно исправить, чтобы метод продолжал корректно работать?

Ответы [ 2 ]

0 голосов
/ 12 сентября 2018

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

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

byteMass = 133333444478126354444
(byteMass.length = 21)
length = 0
    0 (i) < 21 (byteMass.length): true
        count = 0
        1 (j) < 21: true
            1 (byteMass[0 (i + count)]) == 3 (byteMass[1 (j)]): false
                count = 0
        2 (j) < 21: true
            1 (byteMass[0 (i + count)]) == 3 (byteMass[2 (j)]): false
                count = 0
        3 (j) < 21: true
            1 == 3: false

продолжается так, но происходит нечто интересное, когда j = 12 

        12 (j) < 21: true
            1 (byteMass[0 (i + count)]) == 1 (byteMass[12 (j)]): true
                0 (count) >= 0 (length): true
                    length = 1 (count + 1)
                    element = 0 (i)
                    lastElement = 12 (j - count)
                count = 1

По крайней мере, это выглядит как неожиданное поведение!Мы хотим посчитать повторяющиеся числа, но это 1 на 11 цифр от предыдущего 1!Мы можем исправить это, отредактировав внутренний цикл for следующим образом: 

for (int j = i + 1; j < byteMass.length && byteMass[i] == byteMass[j]; j++) {

Таким образом, внутренний цикл прерывается, как только byteMass[i] == byteMass[j] оценивается как false.Теперь давайте перезапустим наш процесс с новым внутренним циклом for 

byteMass = 133333444478126354444
(byteMass.length = 21)
length = 0
    0 (i) < 21 (byteMass.length): true
        count = 0
        1 (j) < 21 && 1 (byteMass[0 (i)]) == 3 (byteMass[1 (j)]): false
    1 (i) < 21: true
        count = 0
        2 (j) < 21 && 3 (byteMass[1 (i)]) == 3 (byteMass[2 (j)]): true
            0 (count) >= 0 (length): true
                length = 1 (0 (count) + 1)
                element = 1 (i)
                lastElement = 2 (2 (j) - 0 (count))
            count = 1 (0 (count) + 1)
        3 (j) < 21 && 3 (byteMass[2 (1 (i) + 1 (count))]) == 3 (byteMass[3 (j)]): true
            1 (count) >= 1 (length): true
                length = 2 (1 (count) + 1)
                element = 1 (i)
                lastElement = 2 (3 (j) - 1 (count))

Это кажется мне неожиданным поведением, но я не буду это исправлять, потому что я не знаю как: я понятия не имею, какой элемент иlastElement представляют.Код продолжается так до тех пор, пока j = 6: 

        6 (j) < 21 && 3 (byteMass[5 (1 (i) + 4 (count))]) == 4 (bteMass[3 (j)]): false
    2 (i) < 21: true
        count = 0
        3 (j) < 21: true
            3 (byteMass[2 (2 (i) + 0 (count))]) == 3 (byteMass[3 (j)]): true
                length = 1 (0 (count) + 1)
                element = 2 (i)
                lastElement = 3 (3 (j) - 1 (count))
            count = 1 (0 (count) + 1)

Это снова будет продолжаться таким же образом до j = 6. На данный момент, надеюсь, вы поймете, почему ваша программа работает не так, как ожидалось.Но я до сих пор не ответил на вопрос, как это исправить.Я не совсем понимаю ваш мыслительный процесс о том, как решить эту проблему, но я поделюсь с вами своими собственными

Прежде всего нам нужно разбить проблему на более мелкие куски !

Вы можете делать это так, как хотите, но вот мой путь: наша цель - найти самый длинный повторяющийся паттерн.Для этого нам нужно выяснить

  1. , когда число повторяется и сколько раз оно повторяется
  2. , если это конкретное число повторяется определенное количество раз в любом местееще в последовательности.Если это произойдет, нам нужно будет сохранить количество повторений, которое оно повторяет
  3. Затем мы повторим процесс, но сохраним данные только в том случае, если количество повторений больше, чем сохраненные данные

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

0 голосов
/ 12 сентября 2018

не проверено.У меня нет IDE передо мной.Изменения от исходного кода.Второй цикл повторяет на один элемент меньше.Если следующий элемент не равен предыдущему, цикл завершается. 

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

                    break;
                 }
            }
        }
...