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 you have read our privacy policy.

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