Palindromic quadruple - ReimuOJ: Reimu Online Judge

Let

S

$S$ be a string consisting only of letters. Count the number of tuples

(i, j, k, t)

$(i, j, k, t)$ such that

1 \leq i \leq j < k \leq t \leq | S |

$1 \leq i \leq j < k \leq t \leq |S|$ and

S [i . . j] + S [k . . . t]

$S[i..j] + S[k...t]$ is a palindrome. ### Input - Only line contains a string

S

$S$ . ### Output - Print the number of quadruples that satisfy the conditions. ### Constraints

| S | \leq 5000

$|S| \le 5000$ ### Example Input:

a a c a

$abbaca$

Output:

14

$14$

Introduction to Dynamic Programming (Part two)
	Sake game
	Coins
	Coins 2
	Game on array
	Longest increasing subsequence 2
	Convolution
	Regular bracket sequence
	Faulty addition
	Weird bank
	Delete operation
	Palindromize
	Color ribbon
	Unique subsequences
	Unique subsequences 2
	Cow exhibition
	Knapsack 3
	Compressing array
	Regular bracket sequence 2
	Maximum path 3
	Concating substring
	Soil
	Stacking boxes
	String transformation
	Palindromic quadruple
	Finding teammates

Topic

Dynamic Programming

String

Rating

1900

Solution (0)

Solution