Text Processor
Inês is new to programming. She is writing a simple application to
handle text. So far, the app only supports adding text to a blank
document. Rita, her restless little sister, is fascinated with all the
different symbols on Inês’ screen and wants to play with it, not letting
Inês work any longer. In order to be able to continue working, Inês
decides to turn it into a game for Rita.
Inês will let Rita write whatever she likes in the app. Then, Inês will
select portions of the document with width W and challenge Rita to
guess how many distinct sequences of symbols there are in that portion
of text. Rita is excited to play, but there is a problem: Inês doesn’t
know yet how to write a program to find the right answer for her own questions. Can you
help her out?
Task
Given the description of the game being played by the two sisters: the text written in the
document, and Inês’ questions, find the number of distinct (non-empty) substrings for each
of the questions. A substring is a sequence of contiguous letters in the document.
Input
The first line of the input contains the text written by Rita. The text is composed only
by letters [a − z]. The second line has two space separated integers: Q and W. Q is
the number of questions and W the fixed width of Inês’ questions. Each of the following
Q lines contains a single integer i, describing a question to know the number of distinct
substrings in the range [i, i + W − 1].
Constraints
1 ≤ |D| ≤ 100 000 Number of letters in a document.
1 ≤ Q ≤ 100 000 Number of questions.
1 ≤ W ≤ |D| Width of Inês’ questions.
1 ≤ i ≤ |D| − W + 1 The question range is one-indexed and inside the document bounds.
Output
The output contains the answer to each question in the same order as in the input, one
per line.
Universidade do Porto Computer Science Department 19
Problem I Problem I
Sample Input 1
acat
2 3
1
2
Sample Output 1
5
6 solve in c++ using decribed solution: Key insight
The number of distinct substrings of a string S is
equal to the length of the edges in its Sux Tree
SWERC Judges Solution Outlines SWERC 2015 28 / 33
I - Text Processor
Base Approach
If we build the sux tree for each query range and count the length
of the tree edges, we can answer all queries.
Problem: building the sux tree for each query would have a
O(Q ⇥ W ) time complexity, which was too slow.
SWERC Judges Solution Outlines SWERC 2015 29 / 33
I - Text Processor
Sample Solution
All queries have the same width W . We can use a sliding window.
The di↵erence between queries i and i + 1 is adding the letter at
position i + W and removing the letter at position i.
If we build the Sux Tree online, e.g. using Ukkonen’s algorithm,
adding a letter follows from the algorithm itself.
Removing a letter in this sliding window is equivalent to removing the
largest sux of the tree. This can be done in O(1) amortized time.
If we keep the sum of the length of the tree edges while we do these
operations, we can answer all queries in O(|D| + Q) time.
SWERC Judges Solution Outlines SWERC 2015 30 / 33
I - Text Processor
Adding a letter
Keep a counter for the number of leaves in the tree.
Adding a letter increases the number of distinct substrings by the
number of leaves in the tree.
If adding a letter creates a new leaf, add that to both counters.
SWERC Judges Solution Outlines SWERC 2015 31 / 33
I - Text Processor
Removing the largest sux
The largest sux is represented in the oldest leaf.
Keep a queue of the leaves created. Remove the leaf in the front.
Delete the edges corresponding to this leaf and update its parents if
necessary