|
|
|
|
|
|
|
| 21 Иванов Андрей Витальевич, 03 ноября 2007 г. 13:48:58 |
алг Кнута-Мориса-Пратта
Вовсе необязательно: ограничения слабые, поэтому подойдет и более простой алгоритм поиска подстроки.
|
|
|
| 22 Гарри Поттер, 22 июня 2007 г. 10:04:41 |
Спасибо, кажется, да :) Если задача получится, то точно да ;) А на второй вопрос, если можно?
Если Вас интересует максимально возможная длина типа string в Delphi, то скажу, что его размер ограничен лишь памятью ЭВМ и может занимать, например, 128Mb что недопустимо во многих задачах, т.к. стандартное ограничение по памяти здесь 16Mb. Принципиально разный подход к типу string в Паскале и в Delphi, хотя суть работы с ними очень сходна. Но есть несколько отличий все же: 1е Вы отметили - это то, что в Delphi строка может быть очень длинной, ну а 2е - это то, что в Паскале ord(s[0]) - это длина строки, а в Delphi подобное обращение вообще не логично и недопустимо.
|
|
|
| 23 Гарри Поттер, 21 июня 2007 г. 9:07:47 |
Поясните, если можно, третий тест: циклический сдвиг аа равен аа и искать его вхождения второй раз не нужно, а 6 получается потому, что в ааааааа есть шесть пересекающихся вхождений аа? Или пересекающиеся вхождения не считаются, а ищется аа (3 раза), сдвигается в аа и ещё получается 3 раза? Надеюсь, вы поняли о чём я. Заранее спасибо. Ещё один вопрос. Из имеющихся здесь обсуждений понятно, что тип string при проверке не ограничен 255 символов, а какова его максимальная длина?
Я Вас понял, конечно. Все пересечения считаются, т.е. строка "аа" входит в "ааааааа" 6 раз. Но после того, как происходит сдвиг строки "аа" мы получаем ту же "аа" и не рассматриваем ее. Нужно рассматривать только разные строки, которые могут получаться из исходной путем сдвига. Хотя это можно понять однозначно: ведь ясно, что рассматривая две подстроки с непустым пересечением мы имеем дело по сути с разными подстроками (несмотря на то, что строки равны могут быть). Ведь у подстроки есть еще позиция ее вхождения в оригинальную строку, тем подстрока и отличается от простой строки. А меня Вы поняли? :)
|
|
|
| 24 Бобер Александр Дмитриевич, 15 марта 2007 г. 9:43:50 |
1) Важна ли неприметная добавочка в условии о содержимом строк?
2) В 3-ем тесте цикл строки аа совпадает с самой строкой и его вхождения не учитываются, а если такая строка 101010?
Задача абсолютно корректна и "неприметная добавочка" вносит некоторую однозначность и не заставляет задумываться о таких символах как символ с кодом 0 или перенос строки. Так что все верно.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
