0字符串中等 NC142 最长重复子串

NC142 最长重复子串

描述

定义重复字符串是由两个相同的字符串首尾拼接而成，例如 便是长度为6的一个重复字符串，而 则不存在重复字符串。

给定一个字符串，请返回其最长重复子串的长度。

若不存在任何重复字符子串，则返回 0 。

分析

想像有两个首尾相连的移动窗口，窗口从左往右遍历，若窗口内的字符串一样，则两条字符串构成重复子串，若遍历完了还没有找到重复子串，则窗口长度减一。为了第一次找到的重复子串就是最长重复子串，窗口长度应该由字符串a的一半开始，慢慢减小。

上述思路是三重循环，第一重：窗口长度遍历；第二重：窗口起点位置遍历；第三重：验证两条窗口内的子串是否相等。

如果枚举到一个字符 i 时判断不满足条件，那么在字符 i 以及它之前的字符为开头的字符串到 i 处都会不满足条件，所以可以从 i + 1 作为开头的字符串继续分析。

因此可以对第二重、第三重进行优化：

验证两个窗口内的字符串时，用变量len记录字符已经相同的个数，若len等于窗口长度，则说明两个窗口内的字符串是相同的，因此找到了最长重复子串。若验证的过程中遇到不一致的情况，则len清零。

这种方法的好处是在验证两条窗口内的字符串是否一致时，顺路移动了窗口的起始位置。

import java.util.*;
public class Solution {
    public int solve (String a) {
        int n = a.length();
        if(n == 0){
            return 0;
        }
        int len = 0;
        for(int i = n / 2; i > 0; i--){
        //为了验证a.charAt(n-i-1) 和a.charAt(n-1)是否相等，所以j应该最大取到n - i
            for(int j = 0; j < n - i; j++){
                if(a.charAt(j) == a.charAt(j+i)){
                    len++;
                }else{
                    len = 0;
                }
                if(len == i){
                    return i*2;
                }
            }
        }
        return 0;
    }
}