Изменения

Перейти к: навигация, поиск

Количество подпалиндромов в строке

108 байт добавлено, 19:35, 19 марта 2016
Нет описания правки
=== Псевдокод ===
'''int''' binarySearch(s : '''string''', center, shift : '''int'''):
''<font color=green>shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1</font>''
'''int''' l = -1, r = s.length, m = 0
'''while''' r - l != 1 m = l + (r - l) / 2 '''if''' hash(s[center - m..center]) == hash(reverse(s[center + shift..center + shift + m])) l = m '''else''' r = m
'''return''' r
'''int''' palindromesCount(s : '''string'''):
'''int''' n = s.length
'''int''' ans = 0
'''for''' i = 0 '''to''' ns.length
ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
'''return''' ans
Анонимный участник

Навигация