| Problem description | | Progress |
Темы:
Z-function. prefix function
In coding theory, unprefixed codes are often used as sets of words, none of which is a prefix. The word α is said to prefix the word β if α is obtained from β by deleting zero or more characters in end. For example, the words a, ab and aba are prefixes of the word aba. For example, the set of words aba, aa and bac is an unprefixed code, while the set of abac, aba< /code>, ba is not present because the word aba is a prefix of the word abac.
Professor Decipher works in the Useless Information Research Lab and studies his new invention of near-prefix codes. A set of words is called an almost prefix-free code of level k if the greatest common prefix of any two words from the set does not exceed k in length. For example, the set abac, abc, ba is a nearly unprefixed level 2 code, and the set abac, abab, ba do not exist because the longest common prefix of abac and abab is 3.
The next task that Professor Decifro set for his laboratory assistants is as follows: given a set of words and a number k, it is required to choose from the given words the maximum set, which is almost prefix-free level code k. You, as a junior laboratory assistant, were assigned to write the corresponding program.
Input
The first line of the input file contains two integers: n and k the number of words in the given set and the level of almost unprefixed code to be built (\(1<= n <= 100000\), \(0 <= k <= 200\)). The next n lines contain one word each. Words consist of lowercase letters of the Latin alphabet. The length of each word is from 1 to 200 characters. The total length of all words does not exceed \(10^6\). All words are different.
Output
Output a single number m - the maximum number of words that can be selected from the given set so that they form an almost unprefixed k level code.
Examples
| # |
Input |
Output |
| 1 |
6 2
aba
bacaba
abacaba
baca
abac
caba
|
3 |
| |
![]()
|
|
Темы:
Z-function. prefix function
Given a non-empty string S whose length N does not exceed \(10^6\). We will assume that the elements of the string are numbered from 1 to N.
For each position of the i character in the string, we will be interested in the substring that ends at that position and matches some beginning of the whole string. Generally speaking, there will be several such substrings, at least two. The longest of them has the length i, we will not be interested in it. And we will be interested in the longest of the remaining such substrings (note that such a substring always exists — in the extreme case, if nothing else is found, an empty substring will do).
The value of the prefix function \(\pi[i]\) will be the length of this substring.
The prefix function is used in various string processing algorithms. In particular, it can be used to quickly solve the problem of finding the occurrence of one string in another ("search for a pattern in the text").
Required for all i from 1 to N to compute \(\pi[i] \).
Input
One string of length N, \(0 < N <= 10^6\), consisting of small Latin letters.
Output
Output N numbers — prefix function values for each position, separated by spaces.
Examples
| # |
Input |
Output |
| 1 |
abracadabra |
0 0 0 1 0 1 0 1 2 3 4 |
| |
![]()
|
|
Темы:
Z-function. prefix function
Arseniy — young promising athlete. Everything that Arseniy likes to do — is to exercise and eat well. He is also punctual. He has just made a schedule of n items: for each of the next n hours, he has decided what he will do at that time — exercise or eat.
Arseniy showed the schedule to his coach, but he did not fully like it. The coach explained that exercising the next hour after eating is unhealthy.
Now Arseniy wants to change his schedule so that he never trains directly after eating. At the same time, he wants to change the minimum number of items on his schedule. Help Arseniy!
Input
The first line of the input contains the number n — number of items in Arseniy's schedule ( 1 ≤ n ≤ 105 ).
The second line contains Arseniy's original timetable. This is a string s of length n , consisting only of Latin letters « t » and « e », and if the letter « t », then this means that at the i-th hour Arseniy planned to train, and if this position is the letter « e », then this means that at the i-th hour Arseniy planned to eat.
Imprint
In the first line print the minimum number of schedule items to be changed.
In the second line print a string of n Latin letters « t » and « e » — modified schedule in the same format as in the input. If there are several suitable schedules, print any of them.
| # |
Input |
Output |
| 1 |
6
tttete |
1
ttteee |
| 2 |
5
tttte |
0
tttte |
| 3 |
9
eeeeetttt |
4
eeeeeeeee |
| |
![]()
|
|
Темы:
Z-function. prefix function
Roma and Denis went to a programming competition. On the long road, the guys remembered operations on strings. Denis said that in Python strings can be multiplied by a number, then Roma, a C++ programmer, decided to come up with a string multiplication operation. According to Roma, the multiplication of a string s of length n by a string t is denoted as s·t and is equal to the string t+s1+t+s2+...+t+ sn+t, where si denotes the i-th character of the string s, and « + " addition (concatenation) of strings is indicated. For example, the product of the strings « abc " and « de» is the string " deadebdecde », but by the product of the lines « z » and « ab » is the string " abzab ". Note that, unlike multiplication of numbers, the product of the strings s and t is not, in general, the product of the strings t and s.
Denis decided to continue the thought of Roma — he, as a connoisseur of beauty, decided to define the beauty of a line as the maximum length of a consecutive group of identical letters. For example, the beauty of the line " xayyaaabca » is 3 because the longest group of consecutive identical letters — it's « aaa », and the beauty of the line « qwerqwer » is equal to 1 because all adjacent letters in it are different.
To entertain Denis, Roma wrote him n lines p1,p2, p3, ... ,pn and asked him to calculate the beauty of the string (...((p1·p2)·p3)· ;...)pn. Denis did not fully understand how Roma's multiplication works, but he does not want to admit it, so he asks you to calculate the beauty of this line. Roma knows that Denis is too impressionable, so he guarantees that the beauty of the resulting string does not exceed 109.
Input
The first line contains the number n (1 ≤ n ≤ 100000) — the number of lines Roma wrote.
The next n lines contain non-empty strings p1, p2, ..., pn, consisting of lowercase English letters.
It is guaranteed that the total length of the strings does not exceed 100000, and also that the beauty of the product of all strings does not exceed 109.
Imprint
Print a single integer — the beauty of the product of lines.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
3
a
b
a |
3 |
The product of three lines is « abaaba » |
| 2 |
2
bn
a |
1 |
The product of two strings is « abanana» |
| |
![]()
|
|
Темы:
Z-function. prefix function
Today at the lesson Petya learned about unprefixed codes. A set of strings is called an unprefixed code if
- All rows in the set are distinct
- There is no pair of distinct strings such that one string is a prefix of the other
The string s is called the prefix of the string t if the length of the string s is not greater than the length of t, and also for any i, the i-th character of the string s matches the i-th character of the string t. For example, ab prefixes ab and abc, but does not prefix a and ac.
Petya decided to come up with something new and introduced a new concept — k-unprefixed code. This code he called a set of lines, such that:
- All rows in the set are distinct
- For any two distinct strings, the longest common prefix has length at most k
The greatest common prefix of two strings s and t is the longest string that is the prefix of both strings.
Now, given the set of strings s1, s2, ..., sn and the number k, Petya wants to find in this set a k-prefix-free code consisting of the maximum possible number of strings. Help him — find this code.
Input
The first line contains two numbers n and k — the number of rows in the set and the maximum length of the common prefix respectively (1 ≤ n ≤ 105, 1 ≤ k ≤ 100).
The i-th of the next n lines contains a string of lowercase Latin letters si — i-th word from the set (1 ≤ |si| ≤ 100).
It is guaranteed that the total length of all strings in the set does not exceed 106.
Imprint
On the first line print the number m - the maximum possible number of lines in k-prefixless
code. In the i-th of the next m lines print the i-th element of this code. Code elements can be displayed in any order.
If there are multiple answers with maximum m, any one is allowed.
| Input |
Output |
5 2
aabc
acbd
aac
acba
aab |
3
aab
aac
acba |
4 2
aa
abc
aa
abb |
3
aa
abb
abc |
Remark
In the first example, strings 1 and 5, as well as strings 2 and 4, have the largest common prefix greater than k, so the maximum number of strings that can consist of a k-prefix-free code is 3. In the second example, any pair of substrings has the largest common prefix no more than 2, however, since the code cannot contain the same lines, more than 3 lines cannot be included in it.
| |
![]()
|
|
Темы:
Dynamic programming
Z-function. prefix function
Chloe wants to write a letter to her friend. Letter - string s, consisting of lowercase Latin letters.
Unfortunately, as soon as Chloe started writing the letter, she realized that it was too long, and it would take a very long time to write it in its entirety. So she wants to write a compressed version of the string s instead of the string itself.
A compressed version of the string s — the sequence of strings c1, s1, c2, s2, ..., ck, sk, where ci — decimal representation of ai (without leading zeros), and si — some string of lowercase Latin letters. If Chloe writes the string s1 exactly a1 times, then s2 exactly a2 times, and so on , it will produce the string s.
The length of the compressed version is |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Among all the compressed versions, Chloe wants to choose the one with the shortest length. Help Chloe find the shortest possible length.
Input:
The single line of the input contains a string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 5000).
Output:
Print a single integer — the minimum length of the compressed version of the string s.
Examples:
| Input |
Output |
| aaaaaaaaaa |
3 |
| abcab |
6 |
| cczabababab |
7 |
Explanations:
In the first example, Chloe will select the following version: c1 — 10, s1 — a.
In the second example, Chloe will choose the following version: c1 — 1, s1 — abcab.
In the third example, Chloe will choose the following version: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.
| |
![]()
|