Sequence (string) consists of repeating another sequence in sliding manner

Question

I have two arrays but will use strings to make the explanation clearer. Need to find out if the first string is a sliding repeating or the second string. Examples (pipes are just for visual delimiting, you may think they don't exist):

Second string is 'abcd'
'abcd|abcd' - yes
'abcd' - yes
'bcd|abcd|ab' - yes
'cd|abc' - yes
'd|a' - yes
'ab' - yes
'сd' - yes

Ok, will try to give another explanation to make it clearer. We have the first string that we need to examine and the second string that is the pattern. We repeat the pattern infinite number of times. If the first string is a substring of ours endless pattern then the answer is yes, otherwise no... Well, seems this additional explanation gives a good hint for the solution!

It's not at all clear what you're asking. Can you explain more clearly? — Jim Mischel, Jun 09 '19 at 06:24
It's still not clear what you're asking. Are delimiters marking a field? Use a better presentation, e.g. `first[] = {100, 200, 300, 400}` — BionicCode, Jun 09 '19 at 07:16
Do you mean something like this: [How can I find matching values in two arrays?](https://stackoverflow.com/questions/12433604/how-can-i-find-matching-values-in-two-arrays)? — BionicCode, Jun 09 '19 at 07:27
@BionicCode think arrays will just clutter the picture. Rephrased this part of topic a little bit, hope it'll eliminate this misunderstanding. — Nick Legend, Jun 09 '19 at 07:30

Nick Legend · Accepted Answer · 2021-03-31T19:20:08.533

After giving my additional explanation came across with the following solution. Function indexOf(...) was taken from source code of java.lang.String and adopted for int[] instead of char[] (really trivial, isn't worth explanation).

    /**
     * Examines if one sequence is a repeating of the other sequence (pattern) in sliding manner.
     * Given are: a sequence that we need to examine, and a pattern. Repeat the pattern infinite number of times.
     * After that if the first sequence is a subsequence of ours endless pattern then the answer is yes, otherwise no.
     * 
     * @param where sequence to be examined
     * @param what pattern
     * @return position in the {@code where} where the pattern starts. Can be outside the {@code where}. See unit 
     *         tests for more details. 
     */
    public static int indexOfSliding(int[] where, int[] what) {

        int multiplier = (int) (Math.ceil((double) where.length / what.length)) + 1;
        int[] biggerWhat = new int[what.length * multiplier];
        for (int i = 0; i < multiplier; i++) 
            for (int j = 0; j < what.length; j++)
                biggerWhat[i * what.length + j] = what[j % what.length];

        int result = indexOf(biggerWhat, where);
        
        if (result == -1) {
            return -1;
        } else {
            return result == 0 ? 0 : what.length - result;
        }
    }

    @Test
    public void testIndexOfSliding() {

        assertEquals(0, Utils.indexOfSliding(new int[] {}, new int[] { 1 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1 }, new int[] {}));
        assertEquals(0, Utils.indexOfSliding(new int[] {}, new int[] {}));

        assertEquals(0, Utils.indexOfSliding(new int[] { 1 }, new int[] { 1 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1 }, new int[] { 2 }));

        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 1 }, new int[] { 1 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1, 1 }, new int[] { 2 }));

        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 2 }, new int[] { 1, 2 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 2, 1 }, new int[] { 1, 2 }));
        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 2, 1 }, new int[] { 1, 2 }));
        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 2, 1, 2 }, new int[] { 1, 2 }));
        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 2, 1, 2, 1 }, new int[] { 1, 2 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 2, 1, 2, 1 }, new int[] { 1, 2 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 2, 1, 2, 1, 2, 1 }, new int[] { 1, 2 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1, 0 }, new int[] { 1, 2 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1, 1 }, new int[] { 1, 2 }));

        assertEquals(0, Utils.indexOfSliding(new int[] {1, 2, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(0, Utils.indexOfSliding(new int[] {1, 2, 3, 1, 2, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 3, 1, 2, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(2, Utils.indexOfSliding(new int[] { 2, 3, 1, 2 }, new int[] { 1, 2, 3 }));
        assertEquals(2, Utils.indexOfSliding(new int[] { 2, 3, 1, 2, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(2, Utils.indexOfSliding(new int[] { 2, 3, 1, 2, 3, 1 }, new int[] { 1, 2, 3 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 3, 2, 1, 2, 3, 1 }, new int[] { 1, 2, 3 }));

        // Pattern bigger than examined sequence, pattern size - 2
        assertEquals(0, Utils.indexOfSliding(new int[] { 1 }, new int[] { 1, 2 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 2 }, new int[] { 1, 2 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 0 }, new int[] { 1, 2 }));
     
        // Pattern bigger than examined sequence, pattern size - 3
        assertEquals(0, Utils.indexOfSliding(new int[] { 1 }, new int[] { 1, 2, 3 }));
        assertEquals(2, Utils.indexOfSliding(new int[] { 2 }, new int[] { 1, 2, 3 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 3 }, new int[] { 1, 2, 3 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 0 }, new int[] { 1, 2, 3 }));
        assertEquals(0, Utils.indexOfSliding(new int[] { 1, 2 }, new int[] { 1, 2, 3 }));
        assertEquals(2, Utils.indexOfSliding(new int[] { 2, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(1, Utils.indexOfSliding(new int[] { 3, 1 }, new int[] { 1, 2, 3 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 1, 3 }, new int[] { 1, 2, 3 }));
        assertEquals(-1, Utils.indexOfSliding(new int[] { 0, 1 }, new int[] { 1, 2, 3 }));
        
    }

Sequence (string) consists of repeating another sequence in sliding manner

1 Answers1