Untitled
unknown
plain_text
2 years ago
1.7 kB
1
Indexable
Never
string solution(string &s) { vector<char> substrings(s.size() * 2 + 1, '#'); for(int i = 0; i != s.size(); ++i){ substrings[i*2 + 1] = s[i]; } int palindromeRadius[substrings.size()]; int radius = 0; int center = 0; int index = 0; int i_mir = 0; int maxLen = 1; for(int i = 1; i != substrings.size() - 1; ++i){ i_mir = 2*center - i; palindromeRadius[i] = radius > i ? min(palindromeRadius[i_mir], radius - i) : 0; while(i > palindromeRadius[i] && (i + palindromeRadius[i] + 1) < substrings.size() && substrings[i - palindromeRadius[i] - 1] == substrings[i + palindromeRadius[i] + 1]) ++palindromeRadius[i]; if(palindromeRadius[i] + i > radius){ center = i; radius = i + palindromeRadius[i]; } if(maxLen < palindromeRadius[i]){ maxLen = palindromeRadius[i]; index = i; } } string result = s.substr((index - maxLen) / 2, maxLen); string changedResult = result; for(int i = 0; i < result.size() / 2; ++i) { if(result[i] - '0' == 0) { changedResult = result.substr(i + 1, result.size() - 2*(i + 1)); } } if(changedResult != result) { if(changedResult.empty()) { result = "0"; } else { result = changedResult; } } else if(result.size() == 1) { int intRes = 0; for(int i = 0; i < s.size(); ++i) { if(s[i] - '0' > intRes) { result = s[i]; intRes = s[i] - '0'; } } } return result; }