Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trie

Count Distinct Substrings

Medium · Trie · Asked at Amazon, Google, Microsoft

Print the number of distinct non-empty substrings of the string.

Input

A single lowercase string s.

Output

The number of distinct non-empty substrings.

Constraints

Insert every suffix into a trie; each newly created node is a new distinct substring. That is O(n²) — much better than storing all substrings in a set.

Example 1

Input

abab

Output

7

Example 2

Input

aaa

Output

3

Hints

  1. Every substring is a prefix of some suffix.
  2. Insert all suffixes into a trie. Each node created corresponds to exactly one new distinct substring — count the nodes.

Approach

For every start index i, walk the trie with s[i..], creating a node whenever a letter is missing and counting it. A trie path equals one distinct substring, so the number of created nodes (excluding the root) is the answer. This is O(n²) time and nodes, versus O(n³) for putting substrings in a hash set. (Suffix arrays/automata do it in O(n log n) or O(n).)

Complexity: O(n²) time · O(n² ) nodes in the worst case

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<array<int, 26>> t(1);
    t[0].fill(-1);
    long long count = 0;
    for (int i = 0; i < n; i++) {
        int cur = 0;
        for (int j = i; j < n; j++) {
            int c = s[j] - 'a';
            if (t[cur][c] < 0) {
                t[cur][c] = t.size();
                t.emplace_back();
                t.back().fill(-1);
                count++;
            }
            cur = t[cur][c];
        }
    }
    cout << count << "\n";
    return 0;
}

Python solution

s = input().strip()
root, count = {}, 0
for i in range(len(s)):
    node = root
    for c in s[i:]:
        nxt = node.get(c)
        if nxt is None:
            nxt = node[c] = {}
            count += 1
        node = nxt
print(count)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String s = new Scanner(System.in).next();
        int n = s.length();
        int maxNodes = n * (n + 1) / 2 + 1;
        int[][] t = new int[maxNodes][];
        t[0] = new int[26];
        Arrays.fill(t[0], -1);
        int size = 1;
        long count = 0;
        for (int i = 0; i < n; i++) {
            int cur = 0;
            for (int j = i; j < n; j++) {
                int c = s.charAt(j) - 'a';
                if (t[cur][c] < 0) {
                    t[size] = new int[26];
                    Arrays.fill(t[size], -1);
                    t[cur][c] = size++;
                    count++;
                }
                cur = t[cur][c];
            }
        }
        System.out.println(count);
    }
}

Solve Count Distinct Substrings online · All practice problems