Problem 6: Suffix Automaton
Problem Statement: Given a string S, construct its suffix automaton and then answer queries about the number of distinct substrings present in S.
Input
A single string S is given in the first line.
Output
Print the number of distinct substrings of S.
Examples
Input:
ababa
Output:
9
Solution Explanation
Method 1: Build the suffix automaton incrementally while processing each character, then count distinct substrings using the difference in lengths between states and their links.
Method 2: The problem can also be solved by constructing the suffix tree and then counting distinct substrings from the edge labels, though this method is more complex to implement.
Solution in C++
#include
#include
#include