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
| #define f(i, a, b) for (int i = a; i <= b; i++)
#define min(a, b) (a < b ? a : b)
char * longestPalindrome(char * s){
char s_new[5000];
int j = 2;
s_new[0] = '$';
s_new[1] = '#';
f(i, 0, strlen(s) - 1)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}
s_new[j++] = '^';
s_new[j] = '\0';
int p[20000]={0};
int center=0, right = 0,maxlen=0,maxcenter=0;
f(i, 2, strlen(s_new))
{
p[i] = i >= right ? 1 : min(right - i, p[2 * center - i]);
while(s_new[i-p[i]]==s_new[i+p[i]]){
p[i]++;
}
if(i+p[i]>right){
right = i + p[i];
center = i;
}
if(maxlen<p[i]){
maxlen = p[i];
maxcenter = i;
}
}
static char res[2000];
j = 0;
f(i, (maxcenter - maxlen) / 2, (maxcenter + maxlen) / 2 - 2)
res[j++] = s[i];
res[j] = '\0';
return res;
}
|