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

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
FatalEagle
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


  • 4
    BenjaminBLi  commented on Sept. 24, 2017, 9:47 p.m. ← edited

    https://codeforces.com/blog/entry/451 Problem E


    • 10
      aeternalis1  commented on Sept. 25, 2017, 2:03 a.m.

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


  • 5
    yantran  commented on April 12, 2016, 10:44 p.m. ← edited

    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?


    • 3
      aeternalis1  commented on Sept. 13, 2017, 6:59 p.m.

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