如题:代码返回最大的回文子串,长度一样返回第一个。
空间效率O(1)
时间效率O(N)(一边遍历搞定)
#include <stdio.h> char* answer; char* maxPalindrome( const char *s ) { bool hasStart = false; int startPos = 0, max = 1, maxStart = 0, maxEnd = 0; for( int i=1; s[i]!='\0'; i++ ) { if( !hasStart ) { if( s[startPos]==s[i] ) { if( i-startPos>max ) { max = i-startPos; maxStart = startPos; maxEnd = i; } continue; } } if( startPos>0 && s[startPos-1]==s[i] ) //李文文指出此处要先检查startPos>0 { startPos--; hasStart = true; } else { if( hasStart==true ) startPos = --i; else startPos = i; hasStart = false; } if( startPos<=0 || i-startPos+1>max ) { max = i-startPos; maxStart = startPos; maxEnd = i; } } int length = maxEnd-maxStart+1; answer = new char[length+1]; for( int i=0; i<length; i++ ) { answer[i] = s[i+maxStart]; } answer[length] = '\0'; return answer; } int main() { char s[10][100] = { "aigbcddcbgaaaaaaaa", "aigbcddcbggggggggg", "aaaaa", "aaaaaa", "aaaaaaaigbcddcbgiaaaaaaa", "a" }; for( int i=0; i<6; i++ ) printf( "%s\n", maxPalindrome(s[i]) ); }
这个自己理解吧,我也不多说了没什么难度。欢迎反馈各种错误 输入例子。