LeetCode 005

题目：LeetCode 005

解法一：马拉车

基于LCR020的算法，只是结果计算部分不一样

    public String longestPalindrome(String s) {int rMax = 0, iMax = 0, len = 0, index = 0;StringBuilder t = new StringBuilder("^#");for (int i = 0; i < s.length(); i++) {t.append(s.charAt(i));t.append('#');}t.append("$");int[] f = new int[t.length() - 1];for (int i = 1; i < t.length() - 1; i++) {f[i] = i <= rMax ? Math.min(f[2 * iMax - i], rMax - i + 1) : 1;while (t.charAt(i + f[i]) == t.charAt(i - f[i])) f[i]++;if (i + f[i] - 1 > rMax) {rMax = i + f[i] - 1;iMax = i;}if (len < f[i] - 1) {index = (i - f[i] + 1) / 2;len = f[i] - 1;}}return s.substring(index, index + len);}

注意：获取子串只需得到子串长度len及其起始索引index，len = f[i] - 1，而index取t中索引除以2即可。