EqualSubstrings2 | Topcoder Archive

Problem Statement

You are given a String s. Compute and return the number of ways in which we can choose two identical non-overlapping substrings of s.

(The two substrings must be non-empty. Each substring must be contiguous.)

Definition

Class:: EqualSubstrings2
Method:: get
Parameters:: String
Returns:: int
Method signature:: int get(String s)
(be sure your method is public)

Constraints

s will consist only of lowercase English letters ('a'-'z').
The length of s will be between 1 and 50, inclusive.

Examples

```
"aa"
```
```
Returns: 1
```
There is exactly one way how to choose two non-empty and non-overlapping substrings. In this case they happen to be equal (both are "a"), so the correct return value is 1.
```
"abcd"
```
```
Returns: 0
```
Regardless how we choose two non-overlapping substrings, they will always differ.
```
"aba"
```
```
Returns: 1
```
One pair: ("a", "a").
```
"abab"
```
```
Returns: 3
```
Three pairs: ("a", "a"), ("b", "b"), ("ab", "ab").
```
"aaaab"
```
```
Returns: 7
```
The 7 ways to select the two equal substrings are shown below. Each row represents one way. The characters 1 and 2 denote characters selected to form the first and second substring, respectively. aaaab ----- 12... 1.2.. 1..2. .12.. .1.2. ..12. 1122. (In the first six ways, the two selected substrings are "a" and "a". In the last way the selected substrings are "aa" and "aa".)
```
"onetwothreeonetwothree"
```
```
Returns: 86
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.