Doubled Fragments

Hard

Call a string *doubled* if it consists of two identical halves, that is, it equals w + w for some non-empty string w. For example, "tictic" and "aa" are doubled, while "tic" and "abba" are not. Given a string text, count how many **distinct** substrings (contiguous pieces) of it are doubled. Equal substrings found at different positions count once.

Example 1

text="xyxyxy" → 2

"xyxy" and "yxyx" qualify. "xyxy" appears twice but is counted once.

Example 2

text="moon" → 1

Only "oo" = "o" + "o" qualifies.

Example 3

text="abc" → 0

Constraints

1 ≤ len(text) ≤ 2000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie String Hash Function Rolling Hash

Similar problems

Framing Word Pairs Hard Counting Distinct Substrings Medium Bookend Word Pairs Easy Target From Word Beginnings Medium Palindrome by Adding Letters in Front Hard

Input

text="xyxyxy"

Expected

Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.