题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。

输入格式
输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 1000000 个小写字符的形式给出。

输入以一个以字符串 END 开头的行表示输入终止。

输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

样例

输入样例：
abcbabcbabcba
abacacbaaaab
END

输出样例：
Case 1: 13
Case 2: 6

算法1

(暴力枚举) $O(n^2)$

yxc 在线教学

时间复杂度

参考文献

JAVA 代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
    static class HashStringTemplate {
        static int base = 131;
        final boolean reverse; //是否倒序计算
        final String line;
        int[] h;
        int[] p;

        public HashStringTemplate(String line, boolean reverse) {
            this.line = line;
            this.reverse = reverse;
            onConstructor();
        }

        /**
         * 构造 hash tables
         */
        void onConstructor() {
            h = new int[line.length() + 1];
            p = new int[line.length() + 1];
            int n = line.length();
            p[0]=1;
            if (!reverse) {
                for (int i = 1; i <= n; i++) {
                    h[i] = h[i - 1] * base + line.charAt(i - 1) - 'a' + 1;
                    p[i] = p[i - 1] * base;
                }
            } else {
                for (int i = 1, j = n - 1; i <= n; i++, j--) {
                    h[i] = h[i - 1] * base + line.charAt(j) - 'a' + 1;
                    p[i] = p[i - 1] * base;
                }
            }
        }

        /**
         * 传进来的下标 从 1开始
         *
         * @param l
         * @param r
         * @return
         */
        long getInternalHashVal(int l, int r) {
            int n = line.length();
            if (!reverse) return h[r] - h[l - 1] * p[r - l + 1];
            else return h[n - l + 1] - h[n - r] * p[r - l + 1];
        }
    }
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
       test2();
    }

    static void test2() {
        String line = sc.next();
        int cnt = 1;
        char extCh = (char) ('z' + 1);
        while (!"END".equals(line) || !line.contains("END")) {
            int ans = 0;
            StringBuilder sb = new StringBuilder();
            for (char c : line.toCharArray()) sb.append(extCh).append(c);
            line = sb.toString();
            HashStringTemplate template_1 = new HashStringTemplate(line, false);
            HashStringTemplate template_2 = new HashStringTemplate(line, true);
            int n = sb.length();
            //1.枚举中心点
            for (int i = 1; i <= n; i++) {
                //2.二分半径
                int l = 0, r = Math.min(i - 1, n - i); //选好左右端点
                while (l < r) {
                    int m = l + r + 1 >> 1;
                    if (template_1.getInternalHashVal(i - m, i - 1)
                            != template_2.getInternalHashVal(i + 1, i + m))r = m - 1;
                    else l = m;
                }
                //注意下标
                if(line.charAt(i-l-1) <= 'z')l++; //二分半径的最后一个点是否满足回文串
                ans = Math.max(ans,l);
            }
            System.out.println("Case " + cnt++ + ": " + ans);
            line = sc.next();
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla