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
|
public int[] manacher(String s){
List<Character> a = new List<>();
a.add('@');
a.add('#');
for (char ch: s.toCharArray()){
a.add(ch);
a.add('#');
}
a.add('?');
int n = a.size();
int maxID = 0;
int id = 0;
int[] p = new int[n];
for (int i = 1; i < n- 1; i++){
if (maxID > i) p[i] = Math.min(p[2 * id - i], maxID - i);
else p[i] = 1;
while (a.get(i - p[i]) == a.get(i + p[i])) p[i]++;
if (i + p[i] > maxID){
maxID = i + p[i];
id = i;
}
}
return p;
}
|