0

ограничение по времени на тест 1 секунда ограничение по памяти на тест 256 мегабайт

В заданной строке найдите длину наибольшей подстроки (отрезка подряд идущих символов строки), которая является палиндромом, то есть одинаково читается слева направо и справа налево. Гарантируется, что заданная строка состоит только из строчных латинских букв.

Входные данные В единственной строке входных данных записана заданная последовательность строчных латинских букв s (1≤|s|≤1000).

Выходные данные Выведите одно целое положительное число — длину наибольшей подстроки-палиндрома.

Примеры

входные данные a выходные данные 1

входные данные zrgttg выходные данные 4

входные данные abacaba выходные данные 7

a,c,ma=input(),'',0
v=0
w=len(a)
for i in range(w):
        for j in range(w):
                c=''
                for k in range(i,j+1):
                        c+=a[k]
                if c==c[::-1]:
                        if len(c)>ma:
                                ma=len(c)


print(ma)

Данная программа не проходит по времени. Подскажите как ее ускорить?

5
  • 1
    Почитайте вот эту статейку: habr.com/ru/post/276195
    – Harry
    28 янв 2020 в 17:52
  • у меня ваша программа выполнилась за 0.0009999275207519531 секунд при вводе 012345678909876543210.
    – n1tr0xs
    28 янв 2020 в 18:11
  • 1
    @n1tr0xs А вы запустите для строки длиной 1000 символов...
    – Harry
    28 янв 2020 в 18:25
  • Мне кажется, но в большинства тестирующих систем есть проблема с замером скорости в python ~10^6 операций за секунду, но самое обидное в том что на С++ этот код пройдёт все тесты, так как там проходит ~10^8 операций в секунду... Но все же, ваш код работает за время O(n^3), такое тут не прокатит.
    – GGO
    28 янв 2020 в 19:13
  • Да просто за квадрат в лоб. Перебор среднего элемента палиндрома и в длину пока можно.
    – pavel
    28 янв 2020 в 21:37

1 ответ 1

0

Вот так можно решить эту задачу (тест с 1000 символов дал подходящий результат):

def findPal(string):
    def findOdd(string):
        max=1
        for Middle in range(len(string)):
            leftBorder = Middle - 1
            rightBorder = Middle + 1
            while(leftBorder >= 0 and rightBorder<len(string) and string[leftBorder] == string[rightBorder]):
                new_str = string[leftBorder:rightBorder+1]
                if len(new_str) >max: max=len(new_str)
                leftBorder-=1
                rightBorder+=1
        return max

    def findEven(string):
        max=1
        for Middle in range(len(string)):
            leftBorder = Middle
            rightBorder = Middle + 1
            while(leftBorder >= 0 and rightBorder < len(string) and string[leftBorder] == string[rightBorder]):
                new_str = string[leftBorder:rightBorder+1]
                if len(new_str) >max: max=len(new_str)
                leftBorder-=1
                rightBorder+=1
        return max

    return max([findOdd(string), findEven(string)])
string=input('Enter string: ')
print(findPal(string))
3
  • Traceback (most recent call last): File "program.pypys3", line 28, in <module> print(findPal(string)) NameError: name 'string' is not defined
    – wargas
    29 янв 2020 в 15:24
  • Вот это выдает.
    – wargas
    29 янв 2020 в 15:25
  • string это ваша строка, которую вводят. Забыл указать
    – n1tr0xs
    29 янв 2020 в 16:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.