codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

159D.md (1485B)


      1 Source: https://codeforces.com/problemset/problem/159/D
      2 
      3 D. Palindrome pairs
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 You are given a non-empty string *s* consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.
     22 
     23 In a more formal way, you have to find the quantity of tuples (*a*, *b*, *x*, *y*) such that 1 ≤ *a* ≤ *b* < *x* ≤ *y* ≤ |*s*| and substrings *s*[*a*... *b*], *s*[*x*... *y*] are palindromes.
     24 
     25 A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.
     26 
     27 A substring *s*[*i*... *j*] (1 ≤ *i* ≤ *j* ≤ |*s*|) of string *s* = *s*1*s*2... *s*|*s*| is a string *s**i**s**i* + 1... *s**j*. For example, substring *s*[2...4] of string *s* = "abacaba" equals "bac".
     28 
     29 Input
     30 
     31 The first line of input contains a non-empty string *s* which consists of lowercase letters ('a'...'z'), *s* contains at most 2000 characters.
     32 
     33 Output
     34 
     35 Output a single number — the quantity of pairs of non-overlapping palindromic substrings of *s*.
     36 
     37 Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 aa
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 1
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 aaa
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 5
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 abacaba
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 36
     75 ```