Подсчёт количества всех палиндромов в строке

Question

Помогите решить проблему. Функция считает количество всех палиндромов в строке (однобуквенные учитываются тоже). Прохожу 11 из 13 тестов на хакерранк, но на двух последних не укладываюсь в лимит по времени. Как можно ускорить выполнение программы:

def CountP(s):
    n = len(s)
    res = 0

    for x in range(n):
        s1 = s[x:n]
        lens = len(s1)
        if s1 == s1[::-1]:                
            res = res + 1

        for i in range(lens - 1):
            subs = s1[:i + 1]
            if subs == subs[::-1]:                   
                res = res + 1


    return res

Спасибо за ответ, но хотя оптимизированный код выполняется намного быстрее, но тоже недостаточно быстро. Может есть еще идеи, как ускорить программу?

def CountP2(s):
    res = 0

    for i in range(len(s) + 1):
        for j in range(i + 1, len(s) + 1):
            t = s[i:j]
            r = ''.join(reversed(t))

            if t == r:
               res = res + 1

    return res

Answer 1

Для подсчёта палиндромов есть линейный алгоритм Манакера. Он компактно выглядит, если входную строку преобразовать, добавив спецсимволы в начале строки и между символами - тогда нужно искать только палиндромы нечётной длины

def countpalindromes(ss):
    s = "$#" + "#".join(ss)+"#"
    n = len(s)
    p = [0] * n
    l = 0
    r = -1
    for i in range(n):
        k = 1 if i > r else min (p[l+r-i], r-i+1)
        while (i+k < n and i-k >= 0 and s[i+k] == s[i-k]):
            k += 1
        p[i] = k
        if (i+k-1 > r):
            l = i-k+1
            r = i+k-1
    return(sum([x//2 for x in p]))

print(countpalindromes("anafana"))
>> 12

БЛОГ НА HUSL

Подсчёт количества всех палиндромов в строке

Ответы (1 шт):