题解 | #最长重复子串#

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

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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param a string字符串 待计算字符串
     * @return int整型
     */
    public int solve (String a) {
        // write code here
        if(a==null)return 0;
        char[]c=a.toCharArray();
        int len=c.length;
        //最大的窗口等于字符串的一半
        int mid=len/2;
        //窗口缩小
        for(int i=mid;i>0;i--){
            //窗口移动
            for(int j=0;j<=len-2*i;j++){
                if(judge(c,j,i)){
                    //最长重复字符串等于一个窗口的长度的两倍
                   return 2*i;
                }
            }
        }return 0;
    }
    boolean judge(char[] c,int left,int len){
        //窗口内的内容比较
        for(int i=left;i<left+len;i++){
            if(c[i]!=c[i+len]){
                return false;
            }
        }return true;
    }
}

复杂度：

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

方法二:优化版本的滑动窗口

未经优化的滑动窗口最坏时间复杂度高达O(n^3),实际上我们可以用一个变量res实时记录重复子串的长度，这里的j不仅作为窗口内指针在移动，比较窗口内容，而且一旦两个窗口内容出现不同时，res置0，窗口的始端移动到下一个字符，所以实质上j还控制着窗口的移动，因此节省了第三重循环，降低时间复杂度，同时，在第一个方法中，无论什么情况下，只要两个窗口中的内容出现不同，窗口每次只会向后移动一个位置，而优化版本中，如果最后一个字符也不同时，第一个窗口直接移动到不同字符的后面，提升了效率
图片说明

import java.util.*;


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

         int mid=a.length()/2;
         //记录窗口长度
         int res=0;
         //窗口长度最长为一半，且不断减小
         for(int i=mid;i>0;i--){
             //j不仅控制着窗口内容的比较，而且控制着窗口的移动，窗口移动的边界条件是字符串长度减去当前的一个窗口长度
             for(int j=0;j<a.length()-i;j++){
                 //比较两个窗口中的字符                                     
                 if(a.charAt(j)==a.charAt(j+i))res++;
                 //一旦出现一个字符不相等时，窗口长度置0，从下一个字符开始遍历
                 else res=0;
                //当结果等于当前一个窗口的长度时，返回窗口长度的两倍
                 if(res==i)return 2*i;
            }
         }
         return 0;
     }
 }

复杂度：

时间复杂度：双重循环，平均时间复杂度为 $图片说明$
空间复杂度：没有辅助空间，常数级的复杂度， $O(1)$