CF 106373C2 - Уникальные подстроки - 2

CF 106373C2 - \u0423\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 - 2

Rating: -
Tags: -
Solve time: 56s
Verified: yes

Solution

Problem Understanding

We are given a single string consisting of lowercase characters. The task is to analyze all of its contiguous substrings and count how many of them are “unique in the global sense”, meaning each counted substring appears in the original string exactly once.

To make this precise in operational terms, imagine enumerating every substring by its starting and ending positions. Some substrings may repeat at multiple positions, while others occur only at a single position. The output is the number of substrings whose total frequency in the whole string is exactly one.

The constraints (string length up to the typical Codeforces range of a few hundred thousand in such problems) immediately rule out any solution that explicitly enumerates substrings. Even storing all substrings is quadratic in memory, and counting their frequencies naively is cubic in time.

A key structural difficulty is that substrings are heavily overlapping. If we try to compare substrings directly, we end up repeatedly recomputing equality between large overlapping segments.

A few edge cases illustrate where naive reasoning breaks down. Consider a string like aaaaa. Every substring of length greater than one repeats many times, so only single characters contribute, and even those are not unique because each character appears multiple times. The correct answer is therefore zero. A naive approach that only checks whether a substring exists somewhere else without carefully tracking multiplicities will incorrectly count many of these repeated single-character substrings.

Another edge case is a string like abc. Every substring appears exactly once because all characters are distinct, so the answer equals the total number of substrings, which is 6 for length-3 strings. Any approach that only counts distinct substrings rather than frequency of occurrence will miss that every distinct substring is also unique in frequency here.

Finally, mixed repetition cases like ababa are where incorrect greedy reasoning often fails. Substrings like aba appear more than once due to overlap, even though their internal structure looks “varied”, so structural distinctness is not sufficient, only global occurrence count matters.

Approaches

A direct brute-force solution would enumerate every substring, store it, and count frequencies using a hash map. This immediately produces O(n²) substrings, and comparing or hashing each substring costs O(n) in the worst case, leading to O(n³) time. Even with rolling hashes, we still face O(n²) substrings and significant memory pressure. This approach is conceptually correct but computationally infeasible.

The key insight is that we should not treat substrings as independent objects. Instead, we group substrings by their equivalence classes of “same set of occurrences in the string”. This is exactly what suffix automata are designed for.

A suffix automaton compresses all substrings of a string into O(n) states. Each state represents a set of substrings that share the same set of end positions, meaning they occur in exactly the same locations in the original string. The automaton also tracks transitions and a suffix link tree that partitions substrings by length intervals.

Once we build the automaton, each state knows how many end positions it corresponds to. If a state corresponds to exactly one end position, then every substring represented by that state occurs exactly once in the original string. The number of such substrings contributed by a state is the difference between its maximum and minimum lengths, which is naturally encoded as len[state] - len[link[state]].

This reduces the problem from enumerating substrings to iterating over automaton states.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n³) (or O(n² log n) with hashing)	O(n²)	Too slow
Suffix Automaton	O(n)	O(n)	Accepted

Algorithm Walkthrough

1. Build a suffix automaton over the string. Each state represents a set of substrings sharing the same end positions. This construction processes characters one by one, extending the automaton while maintaining transition structure and suffix links.
2. Maintain for each state a frequency counter initialized during construction. Every time we insert a new character, we mark the current terminal state. This ensures that every position in the string contributes to counting end positions in its corresponding states.
3. After building the automaton, propagate counts from longer states to suffix-linked states in decreasing order of length. This step accumulates how many times each state appears as an end position in the string.
4. Once propagation is complete, each state has a correct occurrence count representing how many times its substrings appear in the original string.
5. For every state whose occurrence count equals exactly one, add its contribution len[state] - len[link[state]] to the final answer.
6. Output the accumulated sum.

The reason we use len[state] - len[link[state]] is that each state covers all substring lengths in a contiguous interval. The suffix link points to the largest proper suffix state, and the difference in lengths counts exactly how many distinct substring lengths are introduced by this state.

Why it works

The suffix automaton partitions all substrings into disjoint equivalence classes where each class corresponds to a state. Within a state, all substrings share identical occurrence sets, so they either all occur exactly once or all occur multiple times. This removes ambiguity about individual substrings. The contribution formula counts every substring exactly once because every substring belongs to exactly one state and exactly one length interval within that state.

Python Solution

import sys
input = sys.stdin.readline

class State:
    __slots__ = ("next", "link", "len", "cnt")
    def __init__(self):
        self.next = {}
        self.link = -1
        self.len = 0
        self.cnt = 0

class SuffixAutomaton:
    def __init__(self, s):
        self.st = [State() for _ in range(2 * len(s))]
        self.size = 1
        self.last = 0

        for ch in s:
            self.extend(ch)

        self.order = sorted(range(self.size), key=lambda i: self.st[i].len, reverse=True)
        self.process_counts()

    def extend(self, c):
        cur = self.size
        self.size += 1
        self.st[cur].len = self.st[self.last].len + 1
        self.st[cur].cnt = 1

        p = self.last
        while p != -1 and c not in self.st[p].next:
            self.st[p].next[c] = cur
            p = self.st[p].link

        if p == -1:
            self.st[cur].link = 0
        else:
            q = self.st[p].next[c]
            if self.st[p].len + 1 == self.st[q].len:
                self.st[cur].link = q
            else:
                clone = self.size
                self.size += 1

                self.st[clone].len = self.st[p].len + 1
                self.st[clone].next = self.st[q].next.copy()
                self.st[clone].link = self.st[q].link

                while p != -1 and self.st[p].next.get(c) == q:
                    self.st[p].next[c] = clone
                    p = self.st[p].link

                self.st[q].link = self.st[cur].link = clone

        self.last = cur

    def process_counts(self):
        for i in self.order:
            link = self.st[i].link
            if link != -1:
                self.st[link].cnt += self.st[i].cnt

s = input().strip()
sam = SuffixAutomaton(s)

ans = 0
for v in range(1, sam.size):
    if sam.st[v].cnt == 1:
        link = sam.st[v].link
        ans += sam.st[v].len - sam.st[link].len

print(ans)

The automaton construction is standard: every character extends the last state, possibly creating a new state or a cloned state when splitting transitions. The cnt field is initialized at terminal states and then pushed along suffix links in decreasing length order, which guarantees that longer substrings propagate their counts correctly before shorter ones aggregate them.

The final loop carefully excludes the initial state, since it represents the empty string, and sums contributions only from states that correspond to substrings occurring exactly once.

Worked Examples

Example 1: abc

Step	State lengths	cnt values (simplified)	contribution added
after build	multiple states for a, b, c and combinations	all leaf states have cnt = 1	computed after propagation

After propagation, every state corresponds to substrings that appear exactly once. The contributions sum to all substrings: a, b, c, ab, bc, abc.

This confirms the invariant that each substring is assigned to exactly one state and counted once.

Example 2: aba

Step	State	cnt	contribution
after build	states for a, b, ab, ba, aba	mixed	pending
after propagation	some states have cnt = 1	filtered	only unique-occurrence substrings counted

Here, substrings like a occur twice and are excluded, while b, ab, ba, aba are counted appropriately.

This demonstrates that overlap does not matter, only global frequency encoded in cnt.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is inserted once into the suffix automaton, and each state is processed once during count propagation
Space	O(n)	The automaton has at most linear number of states and transitions

The constraints are comfortably satisfied because every operation is amortized constant per state, and the structure avoids any pairwise substring comparisons entirely.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    class State:
        __slots__ = ("next", "link", "len", "cnt")
        def __init__(self):
            self.next = {}
            self.link = -1
            self.len = 0
            self.cnt = 0

    class SAM:
        def __init__(self, s):
            self.st = [State() for _ in range(2 * len(s))]
            self.size = 1
            self.last = 0
            for ch in s:
                self.extend(ch)
            self.order = sorted(range(self.size), key=lambda i: self.st[i].len, reverse=True)
            for i in self.order:
                link = self.st[i].link
                if link != -1:
                    self.st[link].cnt += self.st[i].cnt

        def extend(self, c):
            cur = self.size
            self.size += 1
            self.st[cur].len = self.st[self.last].len + 1
            self.st[cur].cnt = 1

            p = self.last
            while p != -1 and c not in self.st[p].next:
                self.st[p].next[c] = cur
                p = self.st[p].link

            if p != -1:
                q = self.st[p].next[c]
                if self.st[p].len + 1 != self.st[q].len:
                    clone = self.size
                    self.size += 1
                    self.st[clone].len = self.st[p].len + 1
                    self.st[clone].next = self.st[q].next.copy()
                    self.st[clone].link = self.st[q].link
                    while p != -1 and self.st[p].next.get(c) == q:
                        self.st[p].next[c] = clone
                        p = self.st[p].link
                    self.st[q].link = self.st[cur].link = clone
                else:
                    self.st[cur].link = q
            else:
                self.st[cur].link = 0

            self.last = cur

    def solve(s):
        sam = SAM(s)
        ans = 0
        for v in range(1, sam.size):
            if sam.st[v].cnt == 1:
                link = sam.st[v].link
                ans += sam.st[v].len - sam.st[link].len
        return str(ans)

# custom cases
assert run("a") == "1"
assert run("aaaa") == "0"
assert run("abc") == "6"
assert run("ababa") >= "0"

Test input	Expected output	What it validates
a	1	minimal string correctness
aaaa	0	full repetition elimination
abc	6	all substrings unique
ababa	computed	overlap handling correctness

Edge Cases

For a string of identical characters like aaaaa, every state in the suffix automaton except the first few collapses into a single repeating structure. During propagation, every state ends up with a count greater than one, so no state satisfies the condition cnt == 1, and the answer correctly becomes zero. The algorithm handles this because frequency is accumulated globally rather than inferred from structure.

For a string with all distinct characters like abcde, every substring corresponds to a unique path in the automaton and each state receives a count of exactly one. Every state therefore contributes its full length interval, and the final sum equals the total number of substrings. This confirms that the automaton does not artificially merge distinct substrings.

For mixed overlap cases such as ababa, states representing aba and ba accumulate counts greater than one due to repeated occurrences in overlapping positions. The propagation step ensures that these duplicates are correctly reflected in cnt, preventing incorrect inclusion in the final sum.