[hihoCoder#1032]最长回文子串

Wrong Answer:

 1 /************************************************************************/
 2 /* Manacher算法，求解最长回文字符串！                                   */
 3 /************************************************************************/
 4 #include<iostream>
 5 #include<string.h>
 6 using namespace std;
 7  
 8 inline int min(int a,int b){
 9          return a<b?a:b;
10 }
11  
12 /**初始化string，字符间插入‘*’，返回插入后的字符串**/
13 char* transform ( char* str)
14 {
15     const int len=strlen(str);
16     char* newStr=new char[2*len+2];
17     int newlen=0;
18     //newStr[newlen++]='$';
19     for(int i=0;i<len;i++)
20     {
21         newStr[newlen++]='*';
22         newStr[newlen++]=str[i];
23     }
24     newStr[newlen++]='*';
25     //newStr[newlen++]='#';
26     newStr[newlen]='';
27     return newStr;
28 } 
29  //后面与正确版本相同

Accepted:

 1 /************************************************************************/
 2 /* Manacher算法，求解最长回文字符串！                                   */
 3 /************************************************************************/
 4 #include<iostream>
 5 #include<string.h>
 6 using namespace std;
 7  
 8 inline int min(int a,int b){
 9          return a<b?a:b;
10 }
11  
12 /**初始化string，在首位插入‘$’,字符间插入‘*’，返回插入后的字符串**/
13 char* transform ( char* str)
14 {
15     const int len=strlen(str);
16     char* newStr=new char[2*len+4];
17     int newlen=0;
18     newStr[newlen++]='$';
19     for(int i=0;i<len;i++)
20     {
21         newStr[newlen++]='*';
22         newStr[newlen++]=str[i];
23     }
24     newStr[newlen++]='*';
25     newStr[newlen++]='#';
26     newStr[newlen]='';
27     return newStr;
28 } 
29  
30 /**找到str字符串中最长的回文字符串的长度，返回最长长度值**/
31 int manacher (char *str)
32 {  
33     char* pstr=transform(str);
34     const int len=strlen(pstr);
35     int maxR=1;
36     int* r=new int[len];
37     memset(r,0,sizeof(r));
38     int mid=0,lmax=0;
39 
40     for(int i=1;i<len;i++)
41     {
42         if(i<lmax)
43             r[i]=min(r[2*mid-i],lmax-i);
44         else
45             r[i]=1;
46 
47         while(pstr[i-r[i]]==pstr[i+r[i]])
48             r[i]++;
49 
50         if(i+r[i]>lmax)
51         {
52             lmax=i+r[i];
53             mid=i;
54         }
55     }
56 
57     for(int i=1;i<len;i++)
58     {
59         if(r[i]>maxR)
60         {
61             maxR=r[i];
62         }
63     }
64 
65 
66     delete[] r;
67     delete[] pstr;
68     return maxR-1;
69 }
70 
71 
72 int main ()
73 {
74 
75     int num;
76     char str[1000000];
77     cin>>num;
78     for(int i=0;i<num;i++)
79     {
80         cin>>str;
81         cout<<manacher(str)<<endl;
82     }
83     return 0;
84 }