CF 106373C1 - Уникальные подстроки - 1
We are given a string and need to determine how many different non-empty substrings it contains. Two substrings are considered the same if their sequence of characters is identical, even if they appear at different positions.
Rating: -
Tags: -
Solve time: 34s
Verified: yes
Solution
Problem Understanding
We are given a string and need to determine how many different non-empty substrings it contains. Two substrings are considered the same if their sequence of characters is identical, even if they appear at different positions.
The input is a single string over the lowercase English alphabet. The output is the number of unique substring values that can be formed from it.
A direct interpretation of the task suggests taking every possible pair of starting and ending positions, creating that substring, and storing it in a set. This works for small strings, but the number of possible substrings grows quadratically. If the string length is $n$, there are $n(n+1)/2$ substrings by position, and storing their contents can push the total work close to $O(n^3)$. For large values of $n$, this is far beyond what a normal time limit allows.
The tricky cases are strings with many repeated patterns. For example, with input:
aaaa
the answer is:
4
The substrings are a, aa, aaa, and aaaa. A careless solution that counts positions instead of different strings would return 10, because there are 10 possible intervals.
Another case is:
ababa
The answer is:
9
The repeated substrings such as a, b, ab, and aba must only be counted once. Any approach that only checks whether a substring appears before without efficiently representing all previous substrings can become too slow.
A final boundary case is a single character:
x
The answer is:
1
There is exactly one non-empty substring, the string itself.
Approaches
The straightforward method is to generate every substring and insert it into a set. The reason this is correct is simple: a set keeps only one copy of every distinct string, so after processing all intervals its size is the required answer.
The problem is the amount of work. There are $O(n^2)$ substrings, and building each substring may require up to $O(n)$ time. The worst-case complexity becomes $O(n^3)$, which is not suitable when $n$ is large.
The key observation is that substrings are not independent. When we extend a string by one character, many substrings are shared with previous prefixes. A suffix automaton stores exactly the information we need about all substrings of a string while merging equivalent states.
Each state in a suffix automaton represents a group of substrings that have the same set of ending positions. A state stores the maximum length of substrings in that group and the length of the longest suffix represented by its suffix link. The number of new substrings introduced when adding a character is the difference between these two values.
If a state has len[v] as the longest substring length it represents and its suffix link points to link[v], then it contributes:
$$len[v] - len[link[v]]$$
unique substrings. Summing this over all states gives the final answer.
The brute force solution tries to compare strings directly. The suffix automaton instead groups all equivalent substring histories, reducing the work to a linear pass.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(n³) | O(n²) | Too slow |
| Optimal | O(n) | O(n) | Accepted |
Algorithm Walkthrough
- Start with an empty suffix automaton containing only the initial state. This state represents the empty substring.
- Process the characters of the string from left to right. For every new character, extend the automaton by creating a new state that represents all substrings ending at the current position.
- Follow suffix links while there is no transition with the current character. Add the transition from those states to the new state. This records every new substring ending here.
- If an existing transition already exists, check whether the current structure is valid. If the existing state has the wrong length relationship, create a clone state. The clone allows different substrings with the same transitions to be separated correctly.
- After the whole string is inserted, iterate through all states. For every state, add
len[state] - len[link[state]]to the answer. This counts the substring lengths that first appear in that state.
Why it works:
Every distinct substring corresponds to exactly one path in the suffix automaton. A state represents all substrings whose lengths are between len[link[state]] + 1 and len[state]. These lengths are unique new substrings contributed by that state. Since states partition all possible substrings, summing their contributions counts every distinct substring exactly once.
Python Solution
import sys
input = sys.stdin.readline
class State:
__slots__ = ("next", "link", "length")
def __init__(self):
self.next = {}
self.link = -1
self.length = 0
def solve(s):
states = [State()]
last = 0
for ch in s:
cur = len(states)
states.append(State())
states[cur].length = states[last].length + 1
p = last
while p != -1 and ch not in states[p].next:
states[p].next[ch] = cur
p = states[p].link
if p == -1:
states[cur].link = 0
else:
q = states[p].next[ch]
if states[p].length + 1 == states[q].length:
states[cur].link = q
else:
clone = len(states)
states.append(State())
states[clone].next = states[q].next.copy()
states[clone].length = states[p].length + 1
states[clone].link = states[q].link
while p != -1 and states[p].next.get(ch) == q:
states[p].next[ch] = clone
p = states[p].link
states[q].link = clone
states[cur].link = clone
last = cur
ans = 0
for i in range(1, len(states)):
ans += states[i].length - states[states[i].link].length
return ans
s = input().strip()
print(solve(s))
The State object stores the three values required by the automaton. The transition dictionary represents edges labelled by characters, link points to the suffix link, and length stores the longest substring represented by the state.
During insertion, last always points to the state representing the whole processed prefix. When a new character is added, the loop that follows suffix links adds all missing transitions. These transitions correspond to substrings ending at the current character.
The clone creation part is the subtle part of the implementation. Without cloning, two different groups of substrings can incorrectly share a state, causing the final count to be too small. The clone copies transitions but has a smaller maximum length, splitting the groups while preserving the automaton structure.
The final loop starts from state 1 because state 0 represents the empty string. Each state contributes only the lengths that were not already counted by its suffix link.
Worked Examples
For the input:
aaa
the automaton states contribute as follows:
| State | len[state] | len[link[state]] | Contribution |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 2 | 1 | 1 |
| 3 | 3 | 2 | 1 |
The total is:
$$1 + 1 + 1 = 3$$
The distinct substrings are a, aa, and aaa. This trace shows how repeated characters do not create duplicate answers.
For the input:
ab
the states contribute:
| State | len[state] | len[link[state]] | Contribution |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 2 | 0 | 2 |
The total is:
$$1 + 2 = 3$$
The substrings are a, b, and ab. The second state contributes two new lengths because both ab and b end at the new position.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character creates at most two states, and suffix link operations are amortized linear. |
| Space | O(n) | A suffix automaton contains at most 2n - 1 states. |
The algorithm processes every character once and never enumerates substrings explicitly. This is why it remains fast even when the string length is large.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
s = sys.stdin.readline().strip()
return str(solve(s)) + "\n"
assert run("a\n") == "1\n", "single character"
assert run("aaaa\n") == "4\n", "all equal characters"
assert run("ababa\n") == "9\n", "repeated patterns"
assert run("abcde\n") == "15\n", "all substrings are unique"
assert run("aaaab\n") == "9\n", "boundary between repeated and new characters"
| Test input | Expected output | What it validates |
|---|---|---|
a |
1 |
Minimum length handling |
aaaa |
4 |
Duplicate substring elimination |
ababa |
9 |
Overlapping repeated substrings |
abcde |
15 |
Case where every substring is unique |
aaaab |
9 |
Correct transitions after long repetition |
Edge Cases
For aaaa, the algorithm creates a chain of states. Each new state only contributes one additional length because every longer substring is already represented by the previous suffix. The final contributions are 1, 1, 1, and 1, giving the correct answer of 4.
For ababa, repeated occurrences of a, b, and aba are merged into the same automaton states. The contribution formula prevents them from being counted multiple times, so the answer becomes 9 instead of the number of substring positions.
For the single character input x, only one non-empty substring exists. The automaton has one real state with contribution 1 - 0, so it returns 1.