Строка-ссылка (Reference String)
Вам дан список из
n строк, каждая из которых состоит из строчных латинских букв. Мы назовём строку s, состоящую из строчных латинских букв и символа #, строкой-ссылкой (reference string), если для каждой строки из списка можно выбрать некоторый индекс i в s так, что ≠ #, и, взяв все индексы от i до следующего появления # (не включая сам символ #), получить соответствующую строку. При этом строка-ссылка всегда должна заканчиваться символом #.Напишите программу, которая по заданному списку строк определяет длину кратчайшей строки-ссылки, удовлетворя описанному условию.
Ввод
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ 100 000), указывающее количество строк в списке.Следующие
n строк содержат сами строки. Каждая строка состоит из строчных латинских букв и имеет длину не более 10.Вывод
Программа должна вывести одно целое число — длину самой короткой строки-ссылки, удовлетворя условию.
Примеры
Ввод | Вывод |
6
found
profound
ground
round
wound
und | 22 |
3
ab
bc
cd | 9 |
Пояснение
- Пример 1: одна из кратчайших строк-ссылок — это строка ‘ground#profound#wound#’.
- Пример 2: одна из кратчайших строк-ссылок — это строка ‘ab#bc#cd#’.
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB