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 ```