Distinct Echo Substrings

Hard

Return the number of distinct non-empty substrings of s that can be written as the concatenation of some string with itself (i.e. equal to a + a for some string a).

Example 1

Input:  s = "abcabcabc"
Output: 3

Example 2

Input:  s = "leetcodeleetcode"
Output: 2

Example 3

Input:  s = "aaaa"
Output: 2

Constraints

• 1 <= s.length <= 16
• s consists of lowercase English letters.