Diusha 0 31 декабря, 2010 Опубликовано 31 декабря, 2010 · Жалоба Знаю, что такие есть, знаю, что это одна из стандартных задач на олимпиадах по программированию. Но найти не могу. Гугл не захотел помочь. Может кто чем поможет? Хотя бы название или фамилию автора. Алгоритмы с хешированием не подойдут, т.к. подстрока может повторяться не точно Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 1 января, 2011 Опубликовано 1 января, 2011 · Жалоба Может кто чем поможет? Вот здесь посмотрите: Точный поиск подстроки в строке. Ну и весь раздел тоже интересен - Поиск в строках, массивах, последовательностях. Кстати, с Новым годом! :beer: Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 1 января, 2011 Опубликовано 1 января, 2011 · Жалоба Кстати, с Новым годом! :beer: Новым годом! :beer: Вот здесь посмотрите: Ну и весь раздел тоже интересен - Я там уже был. Это не то. Там речь о поиске в строке известного образца Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
ukpyr 0 1 января, 2011 Опубликовано 1 января, 2011 · Жалоба http://algolist.manual.ru/search/lrs/index.php http://kladovka.net.ru/delphibase/?action=...ch&id=10749 http://www.rsdn.ru/forum/alg/752184.flat.aspx Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 1 января, 2011 Опубликовано 1 января, 2011 · Жалоба К сожалению, опять не то. Требуется вот что: Есть строка ABCABCABCABC Из нее нужно выделить минимальный период: ABC (ABCABC тоже период, но уже не минимальный) Есть строка ABCxABCyABCzABC. У этой строки периода нет Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 2 января, 2011 Опубликовано 2 января, 2011 · Жалоба А на сайте Олимпиады по программированию смотрели? Там в библиотеке, в разделе "Алгоритмы на строках" есть две интересные публикации: "Suffix arrays: A new method for on-line string searches" - Udi Manber, Gene Myers (1991) Статья на английском. В ней описан такой мощный инструмент , как суффиксные массивы. Даётся метод с быстродействием O(N * log N) на построение и O(M + log N) на поиск(N - длина строки, в которой ищется подстрока длины М). Алгоритмы которые работают с суффиксными деревьями быстрее, но, как правило, сложнее. "Лекции по информатике" - Дмитрий Павлов (2003) Конспект лекций двукратного чемпиона мира по программированию ACM ICPC, проведенных в рамках подготовки школьников Санкт-Петербурга к всероссийским олимпиадам по информатике. Сделана попытка изложить темы и алгоритмы, которые активно применяются в олимпиадах и которые недостаточно хорошо освещены в доступной литературе по информатике: структуры данных (особенно, деревья Фенвика и отрезков), динамическое программирование, поиск подстроки в строке, проективная геометрия, практические замечания и др. Эти статьи я, на всякий случай, прилагаю. sfx_array.zip informatics_lection.ps Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 3 января, 2011 Опубликовано 3 января, 2011 · Жалоба "Suffix arrays: "Лекции по информатике" - Дмитрий Павлов (2003) 1 - поиск ивестной подстроки - не то Вообще O(N * log N) - больно долго. Видимо, этот алгоритм оправдывает себя в тех случаях, когда в одной строке надо найти кучу образцов (за счет O(M + log N) ). А для разового поиска, по-моему, ничего быстрее КМП не придумали ( O(M+N) на всё - про всё) 2 - пока не сумел посмотреть. Скачал Post Script Viewer, а он .ps не видит Не пoдскажете, чем .ps смотрите? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 3 января, 2011 Опубликовано 3 января, 2011 · Жалоба Не пoдскажете, чем .ps смотрите? Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/ Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 4 января, 2011 Опубликовано 4 января, 2011 · Жалоба Скачайте Ghostscipt + Ghostview - http://pages.cs.wisc.edu/~ghost/ Пока вылезают проблема за проблемой. Возможно, я туповат... Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 4 января, 2011 Опубликовано 4 января, 2011 · Жалоба Может есть альтернативный вариант для просмотра или конвертации ps в pdf или еще во что-нибудь более привычное? Есть самый прямой вариант - Adobe Acrobat (вернее, Distiller). Но вообще странно, с Ghostscipt'ом, обычно, проблем не возникает. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 5 января, 2011 Опубликовано 5 января, 2011 · Жалоба У меня проблемы могут быть везде. Вот и сейчас Акробата установить не могу, т.к. CD-ром сдох (Фокситом пользуюсь) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 5 января, 2011 Опубликовано 5 января, 2011 · Жалоба Вот и сейчас Акробата установить не могу... Ладно, в таком случае я предлагаю воспользоваться онлайн конвертором - PS to PDF - The Online Converter. На всякий случай прилагаю уже обработанный Ghostscipt'ом файл. informatics.pdf Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Diusha 0 6 января, 2011 Опубликовано 6 января, 2011 · Жалоба На всякий случай прилагаю уже обработанный Ghostscipt'ом файл. Спасибо! Лекции интересные, в любом случае пригодятся. Но ответа на конкретный вопрос я так и не нашел Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 7 января, 2011 Опубликовано 7 января, 2011 (изменено) · Жалоба Но ответа на конкретный вопрос я так и не нашел На том же сайте есть книжка: "Программирование: теоремы и задачи." - А.Шень (2004) Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги - научить основным методам построения корректных и быстрых алгоритмов. Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, а также в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ. На всякий случай прилагаю и ее. Кстати, она тоже в PostScript формате. Вообще, могу посоветовать вспомнить хоть какое-то, именно, для искомого алгоритма специфичное слово или понятие. Будет значительно легче. progbookps.zip Изменено 7 января, 2011 пользователем Арташес Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corvinus 0 7 января, 2011 Опубликовано 7 января, 2011 (изменено) · Жалоба Вот еще одна интересная публикация: Анализ строк (String Search) - Graham A. Stephen, October 1992. Хотя этот обзор написан относительно давно, он, судя по всему, еще не потерял актуальности. Перечисленные в нем задачи и методы их решения составляют основу интенсивных исследований. Активные эксперименты с суффиксными деревьями привели к резкому снижений требуемой ими памяти, так что они становятся де-факто стандартом в приложениях, связанных с нестрогим поиском в словарях больших объемов. Список примеров легко продолжить. Конечно, за прошедшие годы проводились многочисленные новые исследования и появились многочисленные новые статьи, не вошедшие в этот обзор. Вместе с тем, конец «периода полураспада» приведенных в нем результатов еще очень далек. Я надеюсь, вы прочтете этот материал с пользой и удовольствием. П.Дубнер Ноябрь 1999 Содержание достаточно заманчивое: 1. ВВЕДЕНИЕ 2. ЗАДАЧА 2.1 Определение задачи 3. ОБЗОР АЛГОРИТМОВ 3.1 Сопоставления строк 3.2 Расстояния между строками 3.2.1 Обобщенные задачи 3.3 Нечеткое сопоставление строк 3.3.1 Специальные устройства 3.4 Максимальная повторяющаяся подстрока 4. АЛГОРИТМЫ 4.1 Поиск образцов 4.1.1 Наивный подход 4.1.2 Кнут-Моррис-Пратт 4.1.3 Бойер-Мур 4.1.4 Бойер-Мур-Хорспул 4.1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение 4.1.6 Хьюм и Сандей.Улучшенные алгоритмы Бойера-Мура и Наименьшая цена 4.1.7 Харрисон 4.1.8 Карп-Рабин 4.2 Расстояние между строками и самая длинная общая подпоследовательность 4.2.1 Вагнер-Фишер 4.2.2 Хиршберг 4.2.3 Хант-Шиманский 4.2.4 Машек-Патерсон 4.2.5 Укконен 4.2.6 Самая тяжелая общая подпоследовательность 4.3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК 4.3.1 k несовпадений - Ландау-Вишкин 4.3.2 k различий - Ландау-Вишкин 4.4 Самая длинная повторяющася подстрока 4.4.1 Наивный подход 4.4.2 Суффиксные деревья 5. НАЗАД, К ИСХОДНОЙ ЗАДАЧЕ 5.1 Система 5.2 Задача 6. ПРИЛОЖЕНИЕ A: АСИМПТОТИЧЕСКАЯ ЗАПИСЬ 7. ЛИТЕРАТУРА Изменено 7 января, 2011 пользователем Арташес Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться