题解 | #最长重复子串#
最长重复子串
http://www.nowcoder.com/practice/4fe306a84f084c249e4afad5edf889cc
描述
- 定义重复字符串是由两个相同的字符串首尾拼接而成,例如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; } }
- 时间复杂度:,三重循环,近似为;
- 空间复杂度:,常数级空间复杂度。
方法二
思路
- 可以将优化方法一的判断是否重复子串的逻辑,减少一层循环从而将时间复杂度降低为。
- 由重复子串的特性可以知道,对于固定长度的重复子串,字符串中每个下标对应的重复子串的右半部分下标也是固定的,所以当判断出从某个下标开始的子串不为重复子串时,其不相等位置之前的字符是不需要重复比较的。
- 所以对于不同长度的重复字符串判断只需要进行一次循环比较即可,对于字符串“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; } }
- 时间复杂度:,双重循环;
- 空间复杂度:,常数级空间复杂度。