文章目录
  1. 1. 暴力枚举
  2. 2. 直接遍历
  3. 3. 统一奇偶
  4. 4. 后缀数组
  5. 5. 求两个字符串的公共子串

【题目】:找出一个字符串中最长的回文,比如goooogleel,最长回文是goooog

暴力枚举

穷举所有的子串,然后找出最长的回文字符串,时间复杂度o(n^3)

直接遍历

遍历整个字符串,然后求出以每个字符为中心的最长回文串(要考虑奇数和偶数问题),这样的时间复杂度为o(n^2);

public String getMaxSym(String str) {
    int index = 0,maxLen = 0, j;
    boolean maxEven = false;
    for (int i=0; i<str.length(); i++) {
        j = 0;
        boolean even = false;
        int eventIndex = 0;

        while (i-j>=0 && i+j<str.length() && str.charAt(i-j) == str.charAt(i+j)) {
            j++;
        }

        if (i+1 < str.length()) {
            while (i-eventIndex>=0 && i+eventIndex+1<str.length() && str.charAt(i-eventIndex) == str.charAt(i+eventIndex+1)) {
                eventIndex++;
            }
        }

        if (2*eventIndex > 2*j-1) {
            even = true;
            if (2*eventIndex >= maxLen) {
                index = i;
                maxLen = 2*eventIndex;
                maxEven = even;
            }
        }   else {
            even = false;
            if (2*j - 1 >= maxLen) {
                index = i;
                maxLen = 2*j - 1;
                maxEven = even;
            }
        }

    }

    if (maxEven) {
        return str.substring(index - (maxLen-2)/2, index + (maxLen+2)/2);
    } else {
        return str.substring(index - (maxLen-1)/2, index + (maxLen+1)/2);
    }
}

统一奇偶

上面的方法比较麻烦的是要区分奇数和偶数,处理比较麻烦。可以使用如下手段进行改进。我们可以这样,在每个字符之间插入一个特殊的字符。
比如字符串:

abcgoogleaba

可以进行这样的操作:

#a#b#c#g#o#o#g#l#e#a#b#a#

代码如下:

public String getMaxSym(String str) {
    if (str == null || str.length() <= 0)
        return str;

    StringBuilder builder = new StringBuilder();
    builder.append("#");
    for (int i=0; i<str.length(); i++) {
        builder.append(str.charAt(i)).append("#");
    }

    str = builder.toString();

    int length = str.length();
    int[] pi = new int[length];
    int index = 0, max = 0;

    for (int i=0; i<length; i++) {
        if (max + index > i) {
            pi[i] = Math.min(max+index-i, pi[2*index-i]);
        } else {
            pi[i] = 1;
        }

        for (;pi[i] + i < length && i-pi[i]>=0 && (str.charAt(i+pi[i]) == str.charAt(i-pi[i])); pi[i]++)
            ;
         if (max < pi[i]) {
             max = pi[i];
             index = i;
         }
    }

    return str.substring(index -max+1,max+index).replace("#", "");
}

后缀数组

将字符串倒转过来,题目就相当于求两个字符串的最长公共子串,题目得到了转化,也不用处理奇偶数。

求两个字符串的公共子串

参考最长公共子串(连续)问题

文章目录
  1. 1. 暴力枚举
  2. 2. 直接遍历
  3. 3. 统一奇偶
  4. 4. 后缀数组
  5. 5. 求两个字符串的公共子串