算法学习-manacher求最长回文子串模板（JAVA实现）

本文最后更新于：April 7, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static char[] s = new char[maxd];
    public static char[] t = new char[maxd*2+5];
    public static int[] p = new int[maxd]; //表示以为中心的回文串半径
    public static int rcen = 0; //记录处理后的串 的回文串 的 中心
    public static int rlen = 0; //分别是记录处理后的串 的回文串 的 长度

    public static int manacher(char[] x) {
        int len = x.length;
        int j = 0;
        t[j++] = '$';
        t[j++] = '#';
        for (int i = 0; i < len; i++) {
            t[j++] = s[i];
            t[j++] = '#';
        }
        t[j] = '\0';
        p[0] = 0;
        int mx = 0, id = 0; //mx表示回文串右端能到的最远下标，id表示回文串的中心
        int ans = 0; //回文串长度
        for (int i = 0; i < j; i++) {
            if (i < mx) p[i] = Math.min(p[id * 2 - i], mx - i); //id*2-i为i关于id的对称点
            else p[i] = 1;
            while (i-p[i]>=0 && t[i - p[i]] == t[i + p[i]]) //先是左边界判断，然后再是关于i的两边是否相等
              p[i]++;
            if (i + p[i] > mx) { //更新回文串右端能到的最远下标
                mx = p[i] + i;
                id = i; //更新回文串中心
                ans = Math.max(ans, p[i] - 1);
            }
            if (p[i] > rlen) { //更新最长的回文串长度
                rlen = p[i];    //这里的rlen就像相当与是ans+1，即这里的p[i]改成p[i]-1后就是ans，即回文串的长度。
                rcen = i;	//这个if判断并不影响ans，只是用来方便记录回文串的位置和长度好在原串中再输出回文串。这里的rlen与ans意思都是一样的，都是回文串的长度
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {

        String str = nextString();
        s = str.toCharArray();
        int n = manacher(s);
        int begin = (rcen - rlen) / 2; //(rcen-rlen)/2 为原串中的起始下标位置
        System.out.println("回文串的长度为 "+n);
        System.out.println("回文串在原串中的起始位置为："+begin+" -> 回文串长度为："+(rlen - 1)); // rlen-1也为回文串的长度，即这里与 n和方法中的ans是相等的,本质看manacher方法中的ans是如何得出的
        for (int i = begin; i < begin+n; i++) {    //输出回文串，等于不能写
            System.out.print(str.charAt(i));
        }
        System.out.println();

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}