Repetitive String Invention

Interview

Time limit2sMemory limit2048 MB

Summary

Count the ways to pick two non-overlapping substrings, in order, whose concatenation is a repetitive string (a square) for a string of length up to 800.

Level: Medium5 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

Lulu has a string of lowercase English letters. She wants to make it Repetitive. A repetitive string has an even number of characters, and its first half exactly matches its second half. For example, "lulu", "abcabc", and "xx" are repetitive, while "xyx" and "abac" are not.

To get a repetitive string, Lulu takes two non-overlapping, non-empty substrings of her string and concatenates them in the order they appear in the string.

In how many ways can she choose two substrings to form a repetitive string? Two ways are different if at least one of the substrings comes from a different part of the string.

Consider the string "aaaa".

There are six ways to form "aa" by matching each "a" with a later "a" ( $1$ + $2$ , $1$ + $3$ , $1$ + $4$ , $2$ + $3$ , $2$ + $4$ , $3$ + $4$ ).
There are three ways to form "aaaa": "a"+"aaa", "aa"+"aa", and "aaa"+"a".

So there are nine ways to form a repetitive string from "aaaa" this way.

Input

The only line contains a string $s$ of lowercase English letters, with $1 ≤ |s| ≤ 800$ .

Output

Print a single integer: the number of ways Lulu can choose two non-overlapping, non-empty substrings and concatenate them in order to get a repetitive string.

Examples2

Example 1
Input
```
aaaa
```
Expected output
```
9
```
Example 2
Input
```
axabxbcxcdxd
```
Expected output
```
22
```