LeetCode 005

标题：LeetCode 005

解法一：马拉车
基于LCR020的算法，只是结果盘算部门不一样

1.     public String longestPalindrome(String s) {
2.         int rMax = 0, iMax = 0, len = 0, index = 0;
3.         StringBuilder t = new StringBuilder("^#");
4.         for (int i = 0; i < s.length(); i++) {
5.             t.append(s.charAt(i));
6.             t.append('#');
7.         }
8.         t.append("$");
9.         int[] f = new int[t.length() - 1];
10.         for (int i = 1; i < t.length() - 1; i++) {
11.             f[i] = i <= rMax ? Math.min(f[2 * iMax - i], rMax - i + 1) : 1;
12.             while (t.charAt(i + f[i]) == t.charAt(i - f[i])) f[i]++;
13.             if (i + f[i] - 1 > rMax) {
14.                 rMax = i + f[i] - 1;
15.                 iMax = i;
16.             }
17.             if (len < f[i] - 1) {
18.                 index = (i - f[i] + 1) / 2;
19.                 len = f[i] - 1;
20.             }
21.         }
22.         return s.substring(index, index + len);
23.     }

复制代码

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