Scribd
Upload
32 views1 page

Problem M - May I Add A Letter?: Input

The document describes a problem where you are given an initial string and a sequence of operations to append letters or delete the last letter from the string. For each resulting string, you must output the number of distinct substrings that occur at least twice.

Uploaded by

Gustavo Lima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views1 page

Problem M - May I Add A Letter?: Input

The document describes a problem where you are given an initial string and a sequence of operations to append letters or delete the last letter from the string. For each resulting string, you must output the number of distinct substrings that occur at least twice.

Uploaded by

Gustavo Lima
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ICPC Latin American Regional – 2020

Problem M – May I Add a Letter?

You have a string S of length N and you are asked to perform a sequence of Q updates of two
types to S:

• Append a given character to the end of S.

• Delete the last character from S.

Initially and after each update, you must calculate the number of distinct strings that occur
at least twice as substrings of S.
For example, if S is initially “ABABC”, the answer is 3, as “A”, “B” and “AB” occur twice as
substrings of S. If you are asked to append the character “C”, S will become “ABABCC” and
the answer will be 4, as now “C” occurs twice too. If you are asked to append “C” again, S will
be “ABABCCC” and the answer will be 5, as “CC” occurs twice now. If you are given a delete
operation now, S will become “ABABCC” and the answer will be 4 again.
Input
The first line contains a string S of length N (1 ≤ N ≤ 105 ), indicating the initial value of
the string. Each character of S is an uppercase letter. The second line contains a string U of
length Q (1 ≤ Q ≤ 105 ), representing the updates to perform. Each character of U is either an
uppercase letter indicating that such a letter must be appended, or the character “-” (hyphen)
denoting a delete operation. The updates must be applied in the order they appear in U . It is
guaranteed that delete operations are not applied to empty strings.
Output
Output Q + 1 lines, each line with an integer indicating the number of distinct strings that
occur at least twice as substrings of S. Line 1 refers to the initial value of S, while line i + 1
refers to the value of S after applying the first i updates (i = 1, 2, . . . , Q).
Sample input 1 Sample output 1

ABABC 3
CC- 4
5
4

Sample input 2 Sample output 2

ABAB 3
A--CC 5
3
1
1
2

Sample input 3 Sample output 3

HAVE 0
FUN 0
0
0

You might also like