Последовательность (строка) состоит из повторения другой последовательности в скользящем порядке

Question

У меня есть два массива, но я буду использовать строки, чтобы сделать объяснение более понятным.Необходимо выяснить, является ли первая строка скользящей повторяющейся или второй строкой.Примеры (каналы предназначены только для визуального разграничения, вы можете подумать, что они не существуют):

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

Хорошо, попробуем дать другое объяснение, чтобы сделать его более понятным.У нас есть первая строка, которую мы должны исследовать, и вторая строка, которая является шаблоном.Мы повторяем образец бесконечное количество раз.Если первая строка является подстрокой нашего бесконечного шаблона, тогда ответ да, в противном случае нет ... Что ж, кажется, это дополнительное объяснение дает хороший совет для решения!

Answer 1

После предоставления моего дополнительного объяснения наткнулся на следующее решение. Функция indexOf(...) была взята из исходного кода java.lang.String и принята для int[] вместо char[] (действительно тривиально, объяснение не стоит).

    /**
     * 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 }));

    }