Даны K строк из маленьких латинских букв. Требуется найти их наибольшую общую подстроку.
В первой строке число K (1 ≤ K ≤ 10). В следующих K строках "— собственно K строк (длины строк от 1 до 10 000).
Наибольшая общая подстрока.
3
abacaba
mycabarchive
acabistrue
cab
Посчитайте, сколько строк над алфавитом из n символов длины m не содержат ни одной подстроки из заданного множества "запрещенных" строк.
В первой строке написаны целые числа n (1 ≤ n ≤ 100) — количество символов в алфавите, m (1 ≤ m ≤ 100) — длина искомых строк и p (0 ≤ p ≤ 10) — количество "запрещенных" подстрок. Следующая строка содержит n символов с кодами больше 32 — буквы алфавита. Далее идет p "запрещенных" строк, длины которых не превосходят min(m, 10) символов. Строки целиком состоят из символов алфавита.
В первой строке выведите ответ на задачу.
2 3 1
ab
bb
5
Данна строка, требуется построить суффиксный массив для этой строки. Суффиксный массив "— лексикографически отсортированный массив всех суффиксов строки. Каждый суффикс задается целым числом "— позицией начала.
Строка s лексикографически меньше строки t, если есть такое i, что si < ti и sj = tj для всех j < i. Или, если такого i не существует и строка s короче строки t.
Здесь si "— код i-го символа строки s.
Файл состоит из единственной строки. Эта строка "— английский литературный текст. Длина текста не превосходит 105. Коды всех символов в тексте от 32 до 127.
Выведите N чисел "— суффиксный массив данной строки.
99 bottles of beer.
14 3 11 19 2 1 15 4 16 17 9 13 8 12 5 18 10 7 6
Задано число n и последовательность из n чисел. Требуется рассмотреть все возможные циклические сдвиги заданной последовательности, отсортировать их в лексикографическом порядке, и вывести сумму наибольших общих префиксов соседних в этом порядке сдвигов.
Входной файл содержит не более 200 тестовых примеров. Каждый тестовый пример состоит из двух строк. Первая из них содержит целое число 1 ≤ n ≤ 50000 — количество магических башен. Вторая строка содержит n чисел в интервале от 0 до 100 — заданную последовательность.
После последнего тестового примера вместо числа n идет 0.
Для каждого тестового примера выведите одно число — искомую сумму.
11
12 8 18 18 8 18 18 8 15 15 8
0
13
Строка называется бинарной, если она состоит только из символов '0' и '1'.
Рассмотрим бинарную строку w длины n. Суффиксным массивом строки w называется массив a[1..n] такой, что строка w[a[i]..n] является i-ым в лексикографическом порядке суффиксом строки w. Например, в результате сортировки суффиксов строки w="001011" они будут расположены следующим образом: "001011", "01011", "011", "1", "1011", "11". Следовательно, суффиксный массив для строки w выглядит так: (1, 2, 4, 6, 3, 5).
Вам дан суффиксный массив a неизвестной строки w. Требуется восстановить строку w.
Первая строка входного файла содержит n — длину строки w (1 ≤ n ≤ 300 000). Вторая строка содержит n различных целых чисел в диапазоне от 1 до n — суффиксный массив строки w.
Выведите единственную строку — искомую бинарную строку w, суффиксный массив которой совпадает с массивом, заданным во входных данных. Если таких строк несколько, выведите любую из них. В случае, если таких строк не существует, выведите "Error".
6
1 2 4 6 3 5
001011