Что не так в элементарном коде для поиска максимального палиндрома? Задача: найти максимальную подстроку палиндром в строке. Т.е.
Входные данные: "wow"
Выходные данные: "wow"
Входные данные: "123wow123"
Выходные данные: "wow"
Входные данные: "abcdebob"
Выходные данные: "bob"
Входные данные: "rokor aba"
Выходные данные: "rokor"
Моё решение, которое не проходит один скрытый тест:bool isSubstringPalindrom(const std::string& str, size_t pos, size_t length)
{
for (size_t i = 0; i < length / 2; ++i) {
if (str[pos + i] != str[pos + length - i - 1])
return false;
}
return true;
}
std::string getStringWithQuotes(const std::string& str)
{
return std::string("\"") + str + "\"";
}
std::string longestPalindromeSubstr(string s) {
if (s.size() 1; --substrLength) {
size_t substringsCount = s.size() - substrLength + 1;
for (size_t i = 0; i < substringsCount; ++i) {
if (isSubstringPalindrom(s, i, substrLength))
return getStringWithQuotes(s.substr(i, substrLength));
std::cout << s.substr(i, substrLength) <
Что не так в элементарном коде для поиска максимального палиндрома? Задача: найти максимальную подстроку палиндром в строке. Т.е.
Входные данные: "wow"
Выходные данные: "wow"
Входные данные: "123wow123"
Выходные данные: "wow"
Входные данные: "abcdebob"
Выходные данные: "bob"
Входные данные: "rokor aba"
Выходные данные: "rokor"
Моё решение, которое не проходит один скрытый тест:bool isSubstringPalindrom(const std::string& str, size_t pos, size_t length)
{
for (size_t i = 0; i < length / 2; ++i) {
if (str[pos + i] != str[pos + length - i - 1])
return false;
}
return true;
}
std::string getStringWithQuotes(const std::string& str)
{
return std::string("\"") + str + "\"";
}
std::string longestPalindromeSubstr(string s) {
if (s.size() 1; --substrLength) {
size_t substringsCount = s.size() - substrLength + 1;
for (size_t i = 0; i < substringsCount; ++i) {
if (isSubstringPalindrom(s, i, substrLength))
return getStringWithQuotes(s.substr(i, substrLength));
std::cout << s.substr(i, substrLength) <
Входные данные: "wow"
Выходные данные: "wow"
Входные данные: "123wow123"
Выходные данные: "wow"
Входные данные: "abcdebob"
Выходные данные: "bob"
Входные данные: "rokor aba"
Выходные данные: "rokor"
Моё решение, которое не проходит один скрытый тест:bool isSubstringPalindrom(const std::string& str, size_t pos, size_t length)
{
for (size_t i = 0; i < length / 2; ++i) {
if (str[pos + i] != str[pos + length - i - 1])
return false;
}
return true;
}
std::string getStringWithQuotes(const std::string& str)
{
return std::string("\"") + str + "\"";
}
std::string longestPalindromeSubstr(string s) {
if (s.size() 1; --substrLength) {
size_t substringsCount = s.size() - substrLength + 1;
for (size_t i = 0; i < substringsCount; ++i) {
if (isSubstringPalindrom(s, i, substrLength))
return getStringWithQuotes(s.substr(i, substrLength));
std::cout << s.substr(i, substrLength) <
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Проблема в вашем коде заключается в том, что он не учитывает возможность наличия нескольких палиндромов максимальной длины в строке.
std::string longestPalindromeSubstr(string s) {Для решения этой проблемы можно модифицировать ваш код, чтобы он сохранял все найденные палиндромы максимальной длины и вернул их все.
Также можно улучшить алгоритм, чтобы он был более эффективным. Например, можно использовать метод расширения палиндромов (expand around center), который быстрее и проще в реализации, чем текущий подход.
Используйте следующую функцию для поиска палиндромов максимальной длины в строке:
if (s.empty()) {
return ""; // если строка пустая, возвращаем пустую строку
}
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
int len1 = expandAroundCenter(s, i, i); // для палиндромов с нечетной длиной
int len2 = expandAroundCenter(s, i, i + 1); // для палиндромов с четной длиной
int len = std::max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substr(start, end - start + 1); // возвращаем найденный палиндром
}
int expandAroundCenter(string s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
Этот код ищет все палиндромы максимальной длины в строке и возвращает первый найденный.