Насчет grep не знаю, а вот что используют программы типа WinHex, работающие с разделами, восстановлением файлов, когда надо прокачать десятки (а то и сотни) гигабайт данных — интересно.
Я пользовалсся Бойер-Муром, но при решении одной из задач все время выскакивал TL. В обсуждениях я прочитал, что надо использовать КМП (в строке поиска и в образце были часто повторяющиеся фрагменты и Б-М не мог быстро «скакать», как я понял из обсуждения). Почитал про КМП, запрограммировал и задача прошла «на ура», а сам КМП запал в душу. Это было давненько, с тех пор я стал использовать его и больше никогда TL не встречался (по причине медленного поиска). Наверное потому, что олимпиадные задачи не требуют чего-то более серьезного.
Полно любителей анонимно минусовать личные комментариии, не им адресованные. Имхо, это минус самого механизма голосования. Такие м**ки отбивают желание и возможность публиковать статьи. Толку, что 100+ пользователей поставили статьи в «избранное»? Они это сделали молча.
Код выводит информацию об нахождении в cout. Получается, что он «заточен» под определенную задачу. С массивом проще — вызывающая прощедура сама решает, что делась с найдеными фрагментами и делает. Хотя можно модифицировать префикс-функцию так, чтобы ее передавала функция, обрабатывающая найденный фрагмент.
Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
Я понял (а точнее, даже вспомнил). В случае, когда надо найти не все вхождения подстроки, а первое вхождение, память нужно выделить для хранения длин префиксов образца. А длины суффиксов строки поиска на запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), функция прекращает работу и возвращает найденную позицию.
Ну, если только упомянуть — так я внес дополнение. Вы удовлетворены? Все же это статья про алгоритм КМП, а не монография про различные методы эффективного поиска.
К сожалению, я неправильно понял Ваше замечание, а редактироване заблокировано. Можете дать ссылку, где памяти требуется O(N)?.. Во всех задачах на acmp, timus (где я использовал КМП) проблем ни с памятью ни со скоростью не было. Но все же интересно.
Даже не заню, что Вам ответить: наверное эта статья не для Вас. Раз требования к памяти возрастают в несколько раз, то Ваши образцы в несколько раз больше строки, где они ищутся.
Написал бы про Байера-Мура — обязательно кто-то спросил бы «прочему не КМП — он ведь такой-разтакой»? Я захотел написать про КМП и написал. Вам нравится Баейр- Мур — так напишите! Зачем противопоставлять одно другому? Чем больше интересных/полезных статей — тем лучше.
Вы меня не огорчили — я в курсе. Это популярная статья для программистов, которым просто нужен быстрый поиск. Процитирую себя: «Но те, кому действительно нужен этот алгоритм, не нуждаются в популярном изложении, имхо».Специалисты по ДНК (или по поиску вирусных сигнатур) относятся именно к тем, на кого это статься не ориентирована.
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
Спасибо за замечание — это проблемы копипаста. Так канительно создавать таблицы. Особенно с цветным выделением, т.к. оно сильно отвлекает внимание. Вроде сейчас поправил.
У MS и яндекса есть свои поисковики, давайте в них «правильные» ссылки. Неужели гугл за свои деньги должен продвигать яндекс, который берет деньги за рекламу и порой такое выдает, что никакого отношения к ключевым словами не имеет.
Что касается сервисов, то гугл мог бы не запрещать производителям предустанавливать свои сервисы вместе с сервисами гугла. А пользователь пусть сам решает, чем пользоваться.
Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кого-то есть такая потребность.
Я не пытаюсь написать статью, которая будет интересна как новичкам, так и «специалистам по глубокому бурению» (имхо, это бесполезно). Как говорил Кузьма Прутков: «И снова повторю — нельзя объять необъятное».
Что касается сервисов, то гугл мог бы не запрещать производителям предустанавливать свои сервисы вместе с сервисами гугла. А пользователь пусть сам решает, чем пользоваться.