Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
kilobitt
0 / 0 / 0
Регистрация: 27.12.2015
Сообщений: 1
#1

Поиск подстроки минимальной длины в строке (файловый ввод/вывод) - C++

27.12.2015, 18:37. Просмотров 256. Ответов 0
Метки нет (Все метки)

Задача I. Рефераты
Имя входного файла: input.txt или стандартный поток ввода
Имя выходного файла: output.txt или стандартный поток вывода
Ограничение по времени: 3 секунды
Ограничение по памяти: 512 мегабайт
Флорен и её друзьям на уроке английского поручили подготовить рефераты по предоставлен-
ным статьям — каждому ученику была выдана отдельная статья, по которой он должен сделать
реферат. В рамках данной задачи статьёй называется непустая строка, состоящая из строчных
символов английского алфавита. Рефератом статьи называется непустая строка, являющаяся под-
строкой данной статьи. Все ученики должны будут представить свои рефераты у доски. Чтобы
их было интереснее слушать, учитель потребовал, чтобы каждый из представленных рефератов не
встречался как подстрока ни в одном тексте статьи, кроме той, из текста которой он был образован.
Так как Флорен и её друзья не любят тратить много времени на выполнение домашнего задания,
они попросили вас помочь им выбрать для каждой статьи реферат минимальной длины, который не
является подстрокой никакой другой статьи, либо сообщить, что выбрать реферат, удовлетворяю-
щий требованию учителя, невозможно. Если для какого-то ученика возможно образовать несколько
кратчайших рефератов, из них требуется выбрать лексикографически минимальный. Вы, конечно
же, согласились им помочь.
Формат входных данных
В первой строке ввода записано одно число n (1 ⩽ n ⩽ 100 000) — количество статей.
Следующие n строк содержат описания статей. Каждая статья представляет собой последова-
тельность строчных символов английского алфавита si (1 ⩽ |si| ⩽ 500 000).
Обозначим через L суммарную длину всех статей, то есть L =∑ni=1|si|. Гарантируется, что во всех тестах L ⩽ 500 000.
Формат выходных данных
Выведите n строк — рефераты, соответствующие указанным статьям, в том же порядке, что и
во входных данных, или символ ‘?’, если для статьи не существует подходящего реферата.
Примеры
ввод
4
bear
deer
read
beard
вывод
?
de
ad
rd
ввод
3
xerox
roxwill
williams
вывод
e
xw
a
я пробовал делать так: брал префикс функцию от каждой строки относительно всех остальных строк, при этом я постепенно уменьшал строку, от которой брал префикс-функцию, удаляя каждый раз по одному начальному символу. И, исходя из этого выбирал нужный минимальный реферат.
вот ссылка на мой код ( если нужно ) http://pastebin.com/tLYYgpk9
Но при моём решение выдаёт long time даже при L=5000 .
Заранее благодарю всех. кто поможет.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2015, 18:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск подстроки минимальной длины в строке (файловый ввод/вывод) (C++):

Написать парсер, разделяющий строки на подстроки (файловый ввод/вывод) - C++
Подкиньте пожалуйста идей для решения задачи

Поиск в массиве структур по заданному полю и вывод в алфавитном порядке (файловый ввод/вывод) - C++
Помогите с функцией void runFile() что бы с файла брал и выводил в алфавитном порядке список товаров, хранящихся больше месяца, стоимость...

Реализовать поиск указанной информации в заданном файле (файловый ввод/вывод) - C++
Сведения об ученике состоят из его имени и фамилии и названия класса (года обучения и буквы), в котором он учится. Дан файл ,содержащий...

Найти и сохранить в каждой строке только те слова, которые удовлетворяют условию (файловый ввод/вывод) - C++
Вечер добрый. Помогите студенту, пожалуйста: завтра экзамен в университете, а на допуск нужно сделать еще одну лабораторную, а я с...

Реализовать сортировку и поиск по заданному полю в массиве пользовательского типа (файловый ввод/вывод) - C++
Подскажите, как реализовать часть задания, которая выделена красным цветом. Построить иерархию классов для контрольных мероприятий,...

Заменить в программе, переводящую строку в двоичный код, консольный ввод/вывод на файловый ввод/вывод - C++
Добрый день! Помогите, пожалуйста, с программой. Программа считывает строку с клавиатуры и переводит её в двоичный код. затем наоборот...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2015, 18:37
Привет! Вот еще темы с ответами:

Файловый ввод/вывод: в строке поменять местами слова, разделенные союзом "и" - C++
Задача такая : для заданной строки S поменять местами слова, разделенные союзом "и". Текст нужно считывать с заранее созданного файла...

Поиск в массиве объектов типа "Student" по заданному полю (файловый ввод/вывод) - C++
Здравствуйте. Стоит такая задача: Создать структуру «студент» со следующими данными: фамилия, имя, отчества, пол, факультет, курс,...

Поиск в массиве объектов типа "Student" по заданному полю (файловый ввод/вывод) - C++
Помогите написать программу 1. Файл содержит итоги контрольного срока, каждая запись которого содержит поля: фамилия студента и средний...

Реализовать поиск в массиве структур "Student" по заданному полю (файловый ввод/вывод) - C++
Помогите написать программы... 1. Пусть на диске текстовый файл ' Hrupa.txt ' , каждая строка которого имеет следующую структуру:...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru