На уроке английского языка Никите совсем нечем было заняться, и он вспомнил о замечательных строках под названием палиндромы. Напомним, что строка называется палиндромом, если она читается одинаково слева направо и справа налево. Примеры таких строк: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».
Никита стал старательно искать все палиндромы в тексте, который они читали в тот момент на уроке. Для каждого вхождения каждого палиндрома он выписывал пару — позицию начала и позицию конца этого вхождения палиндрома в текст. Каждое вхождение каждого палиндрома Никита называет подпалиндромом. Когда Никита нашел все подпалиндромы, ему стало интересно, сколько различных пар из них пересекается. Два подпалиндрома пересекаются, если они содержат общую позицию в тексте, причем считается, что никакой палиндром не пересекается сам с собой.
Рассмотрим на примере текста «babb» все действия, которые делал Никита. Сначала он выписал все подпалиндромы:
• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4 Далее Никита посчитал количество различных пар подпалиндромов, которые пересекаются. Таких пар оказалось шесть:
1. 1..1 пересекается с 1..3 2. 1..3 пересекается с 2..2 3. 1..3 пересекается с 3..3 4. 1..3 пересекается с 3..4 5. 3..3 пересекается с 3..4 6. 3..4 пересекается с 4..4 Так как это всё изнурительно тяжело делать вручную, Никита попросил вас помочь ему и разработать программу, которая по заданному тексту будет определять количество различных пар пересекающихся подпалиндромов. Две пары подпалиндромов называются различными, если есть подпалиндром, который входит в одну из них и не входит в другую.