To solve this problem, we need to determine the number of distinct substrings in a given string. The most efficient way to do this is by using a Suffix Automaton, which allows us to compute the result in linear time and space relative to the length of the string.

Approach

The Suffix Automaton (SA) is a powerful data structure that compactly represents all substrings of a string. The key insight here is that the number of distinct substrings of a string can be derived from the SA by summing the differences between the length of each state and the length of its suffix link.

1. Suffix Automaton Structure: Each state in the SA has:

   • len: The length of the longest substring in the equivalence class of the state.
   • link: A suffix link to another state (representing a shorter substring).
   • trans: A dictionary of transitions from the state to other states via characters.

2. Building the SA: We extend the SA one character at a time, handling new states and cloning existing states when necessary to maintain the automaton's properties.

3. Calculating Distinct Substrings: The number of distinct substrings is the sum of len[state] - len[link[state]] for all states except the initial state (root). This sum accounts for all unique substrings represented by the automaton.

Solution Code

def main():
    size = 1
    last = 0
    len_ = [0]
    link_ = [-1]
    trans = [{}]

    s = input().strip()
    for c in s:
        cur = size
        size += 1
        len_.append(len_[last] + 1)
        link_.append(-1)
        trans.append({})

        p = last
        while p != -1 and c not in trans[p]:
            trans[p][c] = cur
            p = link_[p]

        if p == -1:
            link_[cur] = 0
        else:
            q = trans[p][c]
            if len_[p] + 1 == len_[q]:
                link_[cur] = q
            else:
                clone = size
                size += 1
                len_.append(len_[p] + 1)
                link_.append(link_[q])
                trans.append(trans[q].copy())

                while p != -1 and trans[p][c] == q:
                    trans[p][c] = clone
                    p = link_[p]

                link_[q] = clone
                link_[cur] = clone

        last = cur

    total = sum(len_[u] - len_[link_[u]] for u in range(1, size))
    print(total)

if __name__ == "__main__":
    main()

Explanation

1. Initialization: We start with the root state (size=1, last=0) where len[0] = 0 (no characters), link[0] = -1 (no suffix link), and trans[0] is an empty dictionary.

2. Extending the Automaton: For each character in the input string:

   • Create a new state (cur) with length len[last] +1.
   • Traverse the suffix links from the last state, adding transitions to the new state until we find a state with the current character or reach the root.
   • If we reach the root, set the suffix link of the new state to the root.
   • If we find a state with the current character, check if the next state's length is exactly one more than the current state. If so, link the new state to this next state. Otherwise, clone the next state and adjust the transitions and links accordingly.

3. Calculating the Result: The sum of len[state] - len[link[state]] for all non-root states gives the number of distinct substrings. This is because each state contributes len[state] - len[link[state]] new substrings that end at that state.

This approach efficiently handles large strings (up to 1e5 characters or more) and provides the correct result in linear time. It is optimal for this problem.

作者声明:本文包含人工智能生成内容。