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

View as PDF

Submit solution



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 1 and at most 10^5 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

Comments


  • 0
    BenjaminBLi
     commented on Sept. 24, 2017

    • 0
      aeternalis1
       commented on Sept. 24, 2017

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


  • 2
    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?


    • 0
      aeternalis1
       commented on Sept. 13, 2017

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