- Difficulty: Hard
- Tags: LeetCode, Hard, Trie, String, Hash Function, Rolling Hash, leetcode-1316, Two Pointers, O(n^2 + d), O(r), KMP Algorithm, Sliding Window, Rabin-Karp Algorithm
Problem
Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).
Example 1:
Input: text = "abcabcabc" Output: 3 Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".
Example 2:
Input: text = "leetcodeleetcode" Output: 2 Explanation: The 2 substrings are "ee" and "leetcodeleetcode".
Constraints:
1 <= text.length <= 2000texthas only lowercase English letters.