【模板】Manacher

题目描述

给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。

字符串长度为 $n$。

输入格式

一行小写英文字符 $\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z$ 组成的字符串 $S$。

输出格式

一个整数表示答案。

输入样例 #1

aaa

输出样例 #1

3

输入样例 #2

aedebbbcbbbdbdcbdeacecddaeceddcbbadadbdddaddcaeeaaacbccdeedbebbcedeaddbdbdeaeccedebbdcaadcdedabebbcdcadedbebbdaeecedcdbaddeaaecbebecbdddbaadceaccbeecd

输出样例 #2

7

输入样例 #3

adbeccaddddcdabebcdcacddacddabdaaacaadedbcbccecbadcbabecdcdedabaaabdacbacadcddbceecabcaebdbddccdeacdecdaacdcedcbcceeeeaccebebabeeeacccacbcbcbeacddaaaaecabcacbeeabccecceedcbeeabcaddcbcdaebbabacbeedaaed

输出样例 #3

5

数据范围

$1\le n\le 1.1\times 10^7$。