Обсуждение:Префикс-функция
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Untitled[править код]
неудачную строку выбрали ("abcdabscabcdabia"), т.к. при вычислении префикс-функции не учитывается ситуация с k = p[k-1]. более удачный пример: "aabaaab" с префикс-функцией [0,1,0,1,2,2,3]
Совершенно согласен, пример не полный. Нужен другой пример, охватывающий все пути алгоритма. С этим примером гораздо труднее ухватить суть. Сам и запилю чуть попозже. --John84 13:18, 2 мая 2013 (UTC)
код на Haskell неправильный для строки abcabdxacabcabca должно быть [0,0,0,1,2,0,0,1,0,1,2,3,4,5,3,1]. 87.224.135.5 15:33, 25 октября 2012 (UTC)
код на хаскеле действительно неверный, странно что он вообще иногда работал =) я его немного исправил:
computePrefixFn :: String -> [Int]
computePrefixFn str = helper 0 1 [0]
where
helper :: Int -> Int -> [Int] -> [Int]
helper k i results
| i == length str = results
| otherwise =
if (str !! k) == (str !! i)
then helper (k+1) (i+1) (results ++ [k+1])
else if k == 0
then helper 0 (i+1) (results ++ [0])
else helper (results !! (k-1)) i results
хотя на хаскеле вообще можно обойтись без конструкции if then else/
кроме того, для строки abcabdxacabcabca должно быть [0,0,0,1,2,0,0,1,0,1,2,3,4,5,3,4], что можно проверить вручную, и что дает мой кодец. 188.123.245.11 16:17, 26 января 2013 (UTC)Дима
Дублирующая статья[править код]
А случайно не одно и тоже префикс-функция и Z-функция? 109.73.14.56 13:16, 25 июля 2013 (UTC)
- Нет, они по разному считаются и имеют разный, хотя и похожий, смысл. (обс./вклад) 17:21, 12 августа 2019 (UTC)
АИ?[править код]
Похоже, что предмет статьи значим — она популярна в околопрограммистской среде, скорее всего, с подачи соответствующей статьи на e-maxx. Например, статья про неё есть на вики-конспектах ИТМО, из чего можно сделать вывод, что её там преподают. Проблема в том, что в рецензируемых изданиях эту конструкцию обычно не рассматривают отдельно от алгоритма Кнута — Морриса — Пратта, а там она вообще называется не иначе как Failure function и смысл несёт другой. В связи с этим не вполне ясно, что может выступать АИ по теме. Если есть ещё кто-то, кому тема небезразлична — предлагаю высказаться. (обс./вклад) 17:45, 12 августа 2019 (UTC)