LINUX.ORG.RU

Z функции и префикс функции

 , , ,


0

4

Для поиска подстроки t в строке s с помощью Z функций или префикс функций обычно предполагается создание новой строки вида p=t#s. Существуют ли какие-то красивые модификации позволяющие не создавать p=t#s?

ps: Пока в голову пришло только в лоб понатыкать if-ов и в зависимости от индекса в p(который на самом деле не создан) брать определенный индекс в t или s.

pss: Там префикс и суффикс по идее не могут быть длиннее чем подстрока которую мы ищем насколько я понимаю и половина if-ов не нужно?

Если ты используешь std::string, в libstd++ была CoW реализация, так что новые строки создаваться не будут, только пачка указателей.

hateyoufeel ★★★★★ ()
Последнее исправление: hateyoufeel (всего исправлений: 1)

Существуют ли какие-то красивые модификации позволяющие не создавать p=t#s?

Такая модификация называется KMP.

Пока в голову пришло только в лоб понатыкать if-ов и в зависимости от индекса в p

Бери Boyer-Moore и не страдай фигней.

mix_mix ★★★★★ ()

Быстрее, чем strstr(), вряд ли получится сделать.

PS там как раз Боуэр-Мур, ЕМНИП, как тебе выше посоветовали.

DELIRIUM ★★★★★ ()
Последнее исправление: DELIRIUM (всего исправлений: 1)
Ответ на: комментарий от DELIRIUM

Получится. Алгоритмы в этой области неспроста разрабатывают.

zamazan4ik ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.