描述

定义重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcab则不存在重复字符串。
给定一个字符串，请返回其最长重复子串的长度。
若不存在任何重复字符子串，则返回 0 。

方法一

思路

枚举
重复子串是两个相同的字符串首尾拼接而成，故对于一个长度为n的字符串，其最长的重复子串的长度一定是小于等于n/2的；
对一个字符串，我们可以从其可能的最长重复子串长度开始遍历，也就是从长度为n/2开始遍历，逐渐减少长度，知道找到符合条件的最长重复子串结束。
过程如下：
1.初始化指针i = n/2；
2.初始化指针index = 0；
3.判断（index，index+i-1）与（index+i,index+2i-1）是否相同，相同则为重复子串，由于是从大往小遍历的，所以该重复子串就是最长重复子串，返回长度；
4.不是重复子串，index = index+1；
5.index大于n - i*2，i = i - 1，执行步骤6，反之执行步骤3；
6.i大于等于0，执行步骤2，反之程序运行结束，没有重复子串。

代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 
   * @param a string字符串 待计算字符串
   * @return int整型
   */
  public int solve (String a) {
      int len = a.length();
      // 遍历找出最大的重复子串
      for(int i = len/2;i >= 0;--i){
          for(int index = 0;index <= len - i*2;++index){
              // 判断是否为重复子串
              if (repeated(a,index,i))
                  return 2*i;
          }
      }
      return 0;
  }
  // 判断是否为重复子串
  private boolean repeated(String a,int index,int len){
      for (int i = index;i < index + len;++i){
          // 不为重复子串
          if (a.charAt(i) != a.charAt(i+len))
              return false;
      }
      return true;
  }
}

时间复杂度： $O(n^3)$ ,三重循环，近似为 $O(n^3)$ ；
空间复杂度： $O(1)$ ，常数级空间复杂度。

方法二

思路

可以将优化方法一的判断是否重复子串的逻辑，减少一层循环从而将时间复杂度降低为 $O(n^2)$ 。
由重复子串的特性可以知道，对于固定长度的重复子串，字符串中每个下标对应的重复子串的右半部分下标也是固定的，所以当判断出从某个下标开始的子串不为重复子串时，其不相等位置之前的字符是不需要重复比较的。
所以对于不同长度的重复字符串判断只需要进行一次循环比较即可，对于字符串“ababcc”，当重复子串长度为4时，a[0]对应a[2],a[1]对应a[3],a[2]对应a[4],a[3]对应a[5]。
参考下图示例：
代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 
   * @param a string字符串 待计算字符串
   * @return int整型
   */
  public int solve (String a) {
      int len = a.length();
      int flag = 0;
      // 遍历找出最大的重复子串
      for(int i = len / 2;i > 0;--i){
          for(int j = 0; j < len - i;++j){
              // 判断是否相等
              if (a.charAt(j) == a.charAt(i + j)){
                  ++flag;
              }else{
                  flag = 0;
              }
              // 找到最大重复子串
              if (i == flag){
                  return 2 * i;
              }
          }
      }
      return 0;
  }
}

时间复杂度： $O(n^2)$ ，双重循环；
空间复杂度： $O(1)$ ，常数级空间复杂度。

题解 | #最长重复子串#

描述

方法一

思路

方法二

思路