序列（字符串）由以滑动方式重复另一个序列组成

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

序列（字符串）由以滑动方式重复另一个序列组成

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

arrays

string

algorithm

sequence