Суффиксный массив


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38134. Сбалансированные подмножества
Темы: Динамическое программирование по подстрокам    Суффиксный массив   

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:

Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x1,y) (x2,y) (x1≤x2) есть часть подмножества, то все ячейки (x,y) с x1≤x≤x2 также часть подмножества.
Если ячейки (x,y1) and (x,y2) (y1≤y2) есть часть подмножества, то все ячейки (x,y) with y1≤y≤y2 также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 109+7.

Входные данные: 
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.

Выходные данные: 
Количество сбалансированных подмножеств по модулю 109+7.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 2
GG
GG		 13 Для этого теста все 4-связные подмножества сбалансированные.

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2 4
GGGG
GGGG
GG.G
GGGG		   642
Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию:

GG..
.G..
GG..
....

ID 38511. Путешествие по строке
Темы: Дерево отрезков, RSQ, RMQ    sqrt декомпозиция    Хеш    Суффиксный массив    Динамическое программирование    Хеш   

Скажем, что последовательность строк t1 , ..., tk является путешествием длины k , если для всех i > 1 ti является подстрокой ti - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t1 , ..., tk , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u1 , ..., uk + 1 , такие, что s = u1t1u2 t2 ... uk tk uk + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры
№ Входные данные Выходные данные
1 7
abcdbcc		 3
2 4
bbcb		 2

ID 38645. Оптимальное подмножество строк - 2
Темы: Суффиксный массив   

Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если
- Все строки в множестве различны
- Не существует такой пары различных строк, что одна строка является суффиксом другой
Строка s называется префиксом строки t, если длина строки s не больше длины t, а также для любого i, i-й символ строки s совпадает с i-м символом строки t. Например, ab является префиксом ab и abc, но не является префиксом a и ac.
Петя же решил придумать что-то новое и ввел новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое, что:
- Все строки в множестве различны
- У любых двух различных строк наибольший общий префикс имеет длину не больше k
Наибольшим общим префиксом двух строк s и t называется наибольшая по длине строка, являющаяся префиксом обеих строк.
Теперь по данному множеству строк s1, s2, ..., sn и числу k Петя хочет найти в этом множестве k-бессуффиксный код, состоящий из максимально возможного количества строк. Помогите ему — найдите этот код.
Входные данные
В первой строке содержится два числа n и k — количество строк в множестве и максимальная длина общего префикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100).
В i-й из следующих n строк содержится строка из строчных латинских букв si — i-е слово из множества (1 ≤ |si| ≤ 100).
Гарантируется, что суммарная длина всех строк в множестве не превосходит 106.
Выходные данные
В первой строке выведите число m - максимально возможное количество строк в k-бессуффиксном коде. В i-й из следующих m строк выведите i-й элемент этого кода. Элементы кода можно выводить в любом порядке.
Если существует несколько ответов с максимальным m, разрешается вывести любой.
 

Ввод Вывод
5 2
cbaa
dbca
caa
abca
baa		 3
baa
caa
abca
4 2
aa
cba
aa
bba		 3
aa
bba
cba

Замечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.