F********9
发帖数: 44 | 1 真无语， 不知道哪里有问题。
目测结果都是对的，比如
"a" "a" "a"
"bb" "bb" "bb"
"ccc" "ccc" "ccc"
我的代码哪里有问题？ 希望有高手帮忙：
string longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = s.size();
int *radius = new int[len*2+1];
for (int i=0; i<2*len+1; ++i)
{
radius[i] = 0;
}
char *extend = new char[len*2+2];
for (int i=0, j=0; i
{
extend[j+1] = s[i];
extend[j] = '#';
}
extend[len*2] = '#';
extend[len*2+1] = '\0';
int center=0;
int range=0;
for(int i=1; i
{
int mirror = center - (i-center);
radius[i] = range >= i ?min(range -i, radius[mirror]):0;
while (extend[i-1-radius[i]] == extend[i+1+radius[i]])
++radius[i];
if(radius[i] + i > range)
{
center = i;
range = i+radius[i];
}
}
int maxcenter=0;
int maxradius=0;
for(int i=0; i
{
if(radius[i] > maxradius)
{
maxradius = radius[i];
maxcenter = i;
}
}
delete [] radius;
string ret;
for(int i=maxcenter - maxradius; i
{
if(extend[i] != '#')
{
ret.push_back(extend[i]);
}
}
delete[] extend;
return ret;
} |
|
