Реализуйте структуру данных типа “множество строк”. Хранимые строки – непустые последовательности длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит \(10^{6}\).
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции – один из трех символов: \(+\) означает добавление данной строки в множество; \(-\) означает удаление строки из множества; \(?\) означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит \(10^{6}\). Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.
Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.
| Ввод | Вывод |
|---|---|
+ hello + bye ? bye - bye ? bye ? hello # |
YES NO YES |
Найти все вхождения строки \(T\) в строку \(S\).
Первые две строки входных данных содержат строки \(S \)и \(T\), соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.
Выведите номера символов, начиная с которых строка \(T\) входит в строку \(S\), в порядке возрастания.
| Ввод | Вывод |
|---|---|
ababbababa aba |
0 5 7 |
Мальчик Кирилл написал однажды на листе бумаги строчку, состоящую из больших и маленьких латинских букв, а после этого ушел играть в футбол. Когда он вернулся, то обнаружил, что его друг Дима написал под его строкой еще одну строчку такой же длины. Дима утверждает, что свою строчку он получил циклическим сдвигом строки Кирилла направо на несколько шагов(циклический сдвиг строки abcde на 2 позиции направо даст строку deabc). Однако Дима известен тем, что может случайно ошибиться в большом количестве вычислений, поэтому Кирилл в растерянности – верить ли Диме? Помогите ему!
По данным строкам выведите минимальный возможный размер сдвига или –1, если Дима ошибся.
Первые две строки входного файла содержат строки Кирилла и Димы соответственно. Длины строк одинаковы, не превышают 100000 и не равны 0.
В выходной файл выведите единственное число – ответ на поставленную задачу
| Ввод | Вывод |
|---|---|
a b |
-1 |
zabcd abcdz |
4 |
Дана строка S, состоящая из \(N\) символов. Определим функцию \(A\)(\(i\)) от первых \(i\) символов этой сроки следующим образом:
\(A\)(\(i\)) = максимально возможному \(k\), что равны следующие строки:
S[1]+S[2]+S[3]+…+S[\(k\)]
S[\(i\)]+S[\(i\)–1]+S[\(i\)–2]+…+S[\(i\)–\(k\)+1]
где S[\(i\)] – \(i\)-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.
Напишите программу, которая вычислит значения функции \(A\) для заданной строчки для всех возможных значений \(i\) от 1 до \(N\).
В первой строке входного файла записано одно число \(N\). 1≤\(N\)≤200000. Во второй строке записана строка длиной \(N\) символов, состоящая только из больших и/или маленьких латинских букв.
В выходной файл выведите \(N\) чисел — значения функции \(A\)(1), \(A\)(2), … \(A\)(\(N\)).
| Ввод | Вывод |
|---|---|
5 aabaa |
1 2 0 1 5 |
Строка \(S\) была записана много раз подряд, после чего из получившейся строки взяли подстроку и дали вам. Ваша задача определить минимально возможную длину исходной строки \(S\).
На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 100000 символов.
Требуется вывести одно число – ответ на вопрос задачи.
| Ввод | Вывод |
|---|---|
abaabaabaa |
3 |
Дана непустая строка, длина которой не превышает \(10^{6}\). Требуется для каждой позиции символа в строке найти длину наибольшего палиндрома с центром в этом символе. Строка состоит из букв английского алфавита, большие и маленькие буквы считаются различными. Ограничение времени - 1 секунда.
Одна строка длины \(N\), \(0 \lt N \leq 10^6\).
\(N\) чисел, разделенные пробелами.
| Ввод | Вывод |
|---|---|
abcd |
1 1 1 1 |
aaaaa |
1 3 5 3 1 |
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.
Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.
Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.
Выведите одно число — количество подстрок данной строки, являющихся палиндромами
| Ввод | Вывод |
|---|---|
aaa |
6 |
aba |
4 |