## DMOPC '15 Contest 7 P6 - A Very Very Original Problem

View as PDF

Points:20 (partial)
Time limit:2.0s
Memory limit:64M
Author:

Problem type

Given a string, output the number of nice pairs of special substrings. A special substring is a string that reads the same forwards and backwards. A nice pair of substrings is a pair of substrings that has the following property: after you remove the first substring from the string, you can still remove the second substring from the string (note that neither substring should be contained in the other to be nice).

#### Input Specification

The first and only line of input will contain a string consisting of lowercase letters. The length of the string will be at least and at most characters long.

#### Output Specification

Output the number of nice pairs of special substrings.

#### Sample Input 1

aba

#### Sample Output 1

3

#### Sample Input 2

aaayyylllmmmaaaooo

#### Sample Output 2

570

• BenjaminBLi
commented on Sept. 24, 2017
• aeternalis1
commented on Sept. 24, 2017

Remember, it's not called a very very original problem for nothing.

• yantran
commented on April 12, 2016 edited
To clarify

Can both substrings in a pair of substrings be the same? If you remove the first substring, are you removing all occurrences of it in the string, or just one? For example, in Sample 2 is 'aaa' and 'aaa' a possible pair?

• aeternalis1
commented on Sept. 13, 2017

Yes, 'aaa' and 'aaa' is a possible pair. You only remove that single instance of the substring.