Connorelsea Connorelsea - 4 months ago 16
Java Question

How to find repeating sequence of Integers in an array of Integers?

How to find repeating sequence of Integers in an array of Integers?

00 would be repeating, so would 123123, but 01234593623 would not be.

I have an idea to how to do this, but it is blurry in my mind, and my implementation doesn't go far due to this.

My idea was


  1. Offset by a certain amount each time going through a for loop

  2. Loop through inside of that and compare chunks of numbers by that offset



In Java, I got this far:

String[] p1 = new String[nDigitGroup];
String[] p2 = new String[nDigitGroup];

for (int pos = 0; pos < number.length - 1; pos++)
{
System.out.println("HERE: " + pos + (nDigitGroup - 1));
int arrayCounter = -1;

for (int n = pos; n < pos + nDigitGroup ; n++)
{
System.out.printf("\nPOS: %d\nN: %d\n", pos, n);
arrayCounter++;
p1[arrayCounter] = number[n];

System.out.println(p1[arrayCounter]);
}

pos += nDigitGroup;
arrayCounter = -1;

System.out.println("SWITCHING");

for (int n = pos; n < pos + nDigitGroup ; n++)
{
System.out.printf("\nPOS: %d\nN: %d\n", pos, n);
arrayCounter++;
p2[arrayCounter] = number[n];

System.out.println(p2[arrayCounter]);
}

if (p1[0].equals(p2[0]) && p1[1].equals(p2[1])) System.out.println("MATCHING");
}


When ran with these arguments:

repeatingSeqOf(2, new String[] {"1", "2", "3", "4", "5", "6", "7", "7" });


I am correctly filling the section arrays, but it breaks on an index out of bounds exception.

Answer

@MiljenMikic answer's is great, especially since the grammar isn't actually regular. :D

If you want to do it on an array in general, or want to understand it, this does pretty much exactly what the regex does:

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3, 2, 3}; // 2, 3 repeats at position 2.

    // for every position in the array:
    for (int startPos = 0; startPos < arr.length; startPos++) {
        // check if there is a repeating sequence here:

        // check every sequence length which is lower or equal to half the
        // remaining array length: (this is important, otherwise we'll go out of bounds)
        for (int sequenceLength = 1; sequenceLength <= (arr.length - startPos) / 2; sequenceLength++) {

            // check if the sequences of length sequenceLength which start
            // at startPos and (startPos + sequenceLength (the one
            // immediately following it)) are equal:
            boolean sequencesAreEqual = true;
            for (int i = 0; i < sequenceLength; i++) {
                if (arr[startPos + i] != arr[startPos + sequenceLength + i]) {
                    sequencesAreEqual = false;
                    break;
                }
            }
            if (sequencesAreEqual) {
                System.out.println("Found repeating sequence at pos " + startPos);
            }
        }
    }
}