马拉车

O(n)求字符串中的最长回文串的长度
 1 char s[SIZE];
 2 int len[SIZE*2];
 3 char str[SIZE*2];
 4 int manacher(){//预处理字符串，将字符串隔开,且开头和结尾字符串要不同,防止越界，如aaa预处理为@#a#a#a$
 5        int l = strlen(s);
 6     int ls = 0;
 7     str[ls++] = '@';
 8     for(int i=0;i<l;i++){
 9         str[ls++] = '#';
10         str[ls++] = s[i];
11     }
12     str[ls++] = '#';
13     str[ls++] = '$';
14     str[ls] = '';
15     int mx=0,po=0;
16     int ans = -1;
17     for(int i=1;i<ls-1;i++){
18         if(i<mx) len[i] = min(mx-i,len[po*2-i]);
19         else len[i] = 1;
20         while(str[len[i]+i] == str[i-len[i]])
21             len[i]++;
22         if(len[i]+i>mx){
23             mx = len[i]+i;
24             po = i;
25         }
26         ans =max(ans,len[i]);
27     }
28     return ans - 1;
29 }