owned this note
owned this note
Published
Linked with GitHub
```java =
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class LongestPalindrome {
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static class Reader {
private BufferedReader br;
private String content;
private StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public boolean hasNext() throws IOException {
if (st != null && st.hasMoreTokens())
return true;
boolean next = (content = br.readLine()) != null && !content.isEmpty();
if (next)
st = new StringTokenizer(content);
return next;
}
public String next() {
try {
hasNext();
} catch (IOException e) {
}
return st.nextToken();
}
}
static long MOD = (long) (1e9 + 7);
static int N = 27;//(int) (1e6 + 6);
static long x = 31;
static long pw[] = new long[N]; // pw[i] = x^i % MDO
static long v [] = new long[N];
private static void make_hash(String s) { // s is 1-based
int n = s.length();
for (int i = 1; i < n; i++) {
v[i] = (s.charAt(i) - 'a' + 1) * pw[i];
}
// prefix sum
for (int i = 1; i < n; i++) {
v[i] = (v[i - 1] + v[i]) % MOD;
}
}
private static void build(String s){
pw[0] = 1;
for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * x % MOD;
make_hash(s);
}
private static boolean query(int l, int r, int l1, int r1){
return (v[r] - v[l])* pw[l1] % MOD == (v[r1] - v[l1])% MOD;
}
public static void main(String[] args) throws IOException {
Reader reader = new Reader();
int max = 0;
while(reader.hasNext()){
String s = reader.next();
build(s + reverse(s));
int n = s.length();
for(int i = 0; i < n; i ++){
for(int j = i; j < n; j++){
if(query(i, j, 2 * n - 1 - i, 2 * n - 1 - j)){
max = Math.max(max, j - i + 1);
}
}
for(int j = i + 1; j < n; j++){ // 偶數長度會有中心點 [i, i+1]
if(query(i, j, 2 * n - 1 - i, 2 * n - 1 - j)){
max = Math.max(max, j - i + 1);
}
}
// int l = 1;
// int r = n;
//
// while(l < r){
// int len = (l + r)/2;
// int j = len + i;
// if(!query(i, j, 2 * n - 1 - i, 2 * n - 1 - j)){
// r = len;
// }else{
// l = len + 1;
// }
// }
// max = Math.max(max, l - 1);
//
// l = 1;
// r = n;
//
// while(l < r){
// int len = (l + r)/2;
// int j = len + i + 1;
// if(!query(i, j, 2 * n - 1 - i, 2 * n - 1 - j)){
// r = len;
// }else{
// l = len + 1;
// }
// }
// max = Math.max(max, l - 1);
}
}
out.println(max);
out.flush();
}
private static String reverse(String s){
StringBuilder sb = new StringBuilder(s);
sb.reverse();
return sb.toString();
}
}
```
### Updated
```java=
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class LongestPalindrome {
static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
static class Reader {
private BufferedReader br;
private String content;
private StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public boolean hasNext() throws IOException {
if (st != null && st.hasMoreTokens()) return true;
boolean next = (content = br.readLine()) != null && !content.isEmpty();
if (next) st = new StringTokenizer(content);
return next;
}
public String next() {
try {
hasNext();
} catch (IOException e) {
}
return st.nextToken();
}
}
static long MOD = (long) (1e9 + 7);
static int N = (int) (1e6 + 6);
static long x = 31;
static long pw[] = new long[N]; // pw[i] = x^i % MDO
static long ipw[] = new long[N]; // pw[i] = x^i % MDO
static long v[] = new long[N];
private static void make_hash(String s) { // s is 1-based
int n = s.length();
for (int i = 1; i < n; i++) {
v[i] = (s.charAt(i) - 'a' + 1) * pw[i];
}
// prefix sum
for (int i = 1; i < n; i++) {
v[i] = (v[i - 1] + v[i]) % MOD;
}
}
private static void build(String s) {
pw[0] = 1;
for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * x % MOD;
// 模逆元
ipw[0] = 1;
ipw[1] = pow(x, MOD - 2, MOD); // x^-1 = x 的 P-2 mod P
// 費馬小定理
for (int i = 1; i < N; i++) ipw[i] = ipw[i - 1] * ipw[1] % MOD;
make_hash(s);
}
private static boolean query(int l, int r, int l1, int r1) {
long h1 = (v[r] - v[l - 1] + MOD) * ipw[l - 1] % MOD; // +MOD 可以確保結果是正數
long h2 = (v[r1] - v[l1 - 1] + MOD) * ipw[l1 - 1] % MOD;
return h1 == h2;
}
private static boolean isPal(int n, int l, int r) {
// [l, r] is 1-base
return query(l, r, 2 * n + 1 - r, 2 * n + 1 - l);
}
public static void main(String[] args) throws IOException {
Reader reader = new Reader();
int max = 0;
while (reader.hasNext()) {
String s = reader.next();
build(" " + s + reverse(s));
int n = s.length();
for (int i = 1; i <= n; i++) {
for (int l = i, r = i; l >= 1 && r <= n; l--, r++) {
if (isPal(n, l, r)) {
max = Math.max(max, r - l + 1);
}
}
for (int l = i, r = i + 1; l >= 1 && r <= n; l--, r++) {
if (isPal(n, l, r)) {
max = Math.max(max, r - l + 1);
}
}
}
}
out.println(max);
out.flush();
}
private static String reverse(String s) {
StringBuilder sb = new StringBuilder(s);
sb.reverse();
return sb.toString();
}
}
```