题解 | #最长重复子串#

描述
一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。
从题目中我们可以整理出以下关键点：
1.一个重复字符串是由两个连续的相同的字符串首尾拼接而成，这里很容易出现一个误区觉得的最长重复子串是3，然而在本题根据题意，答案是2，最长重复字符串是前面的或者
后面的。
2.如果存在最长重复字符串，它的长度一定是偶数
3.不存在重复字符串或者字符串是，返回0
方法一：滑动窗口
子串问题一般都是用滑动窗口解决，这里就是一个典型的例子，

我们先将字符串从中间分开，看成两个连续的窗口，最大窗口的长度是字符串长度的一半，
函数比较窗口中的内容是否相等，如果相等，返回true，此时的最长重复子串长度等于一个窗口的长度的两倍，即2*i;否则继续移动窗口，移动步数的边界是字符串长度减去此时的两个窗口长度；
在这一层窗口长度中找不到重复子串则缩小窗口长度，重复步骤2，直到窗口长度缩小至0，循环结束

复杂度：

时间复杂度：存在三层循环，第一层控制窗口大小，第二层控制窗口的移动，第三层判断两个窗口中的内容是否相等，时间复杂度最坏达图片说明
空间复杂度：没有额外的辅助空间，

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String a) {

        if (a == null || a.length() == 0) {
            return 0;
        }

        int mid = a.length() / 2;

        char[] chars = a.toCharArray();

        //记录窗口长度
        int compareWindowCharacterLen = 0;

        for (int windowSize = mid; windowSize > 0; windowSize--) {

            for (int windowStepIndex = 0; windowStepIndex <= (a.length() - 2 * windowSize); windowStepIndex++) {
                   //方法1时间复杂度 O(n的3次方)
//                 if (compareWindowCharacters(chars, windowStepIndex, windowSize)) {
//                     return 2 * windowSize;
//                 }

                //方法2时间复杂度 O(n的2次方)
                if (chars[windowStepIndex] == chars[windowStepIndex+windowSize]) {
                    compareWindowCharacterLen++;
                } else {
                    //一旦出现一个字符不相等时，窗口长度置0，从下一个字符开始遍历
                    compareWindowCharacterLen = 0;
                }

                if (compareWindowCharacterLen == windowSize) {
                    return 2 * windowSize;
                }
            }

        }
        return 0;
    }

    public boolean compareWindowCharacters (char[] chars, int windowStepIndex, int windowSize) {

        for (int i = windowStepIndex; i < windowSize + windowStepIndex; i++) {

            if (chars[i] != chars[i+windowSize]) {
                return false;
            }
        }
        return true;
    }
}