P2408 Number of Distinct Substrings

After getting crushed by NOI, the "ju ruo" (rookie) YJQ decided to study strings and came across this problem.

Given a string of length $n$, find the number of distinct substrings. We define two substrings to be different if and only if either their lengths are different, or their lengths are the same but there exists at least one position where they differ. A substring is defined as a contiguous segment of characters in the original string.

The first line contains an integer $n$. The second line contains $n$ characters representing the given string.

Output a single integer in one line, representing the number of distinct substrings.

Please use a 64-bit integer for the output. Constraints - For 30% of the testdata, $n \le 1000$. - For 100% of the testdata, $1 \leq n \le 10^5$, and the string contains only lowercase English letters. Translated by ChatGPT 5