Строковые алгоритмы: наивный поиск, КМП, Z-функция, Рабин — Карп, Ахо — Корасик — авторское изложение

ru · official · sha256:717fa7ed13b839f598b11efeec32d4d75c6434728dae3915867dbbe30e116c2aRU

§1. Строка, образец, сдвиг и границы Строка длины n есть последовательность символов из конечного алфавита, занумерованных с нуля. Подстрока, начинающаяся в позиции i и имеющая длину m, есть последовательность символов позиций от i до i + m − 1. Вхождение образца длины m в текст длины n есть позиция i, при которой подстрока текста этой длины совпадает с образцом посимвольно. Позиция вхождения указывает на его НАЧАЛО; соглашение названо явно, потому что часть изложений указывает конец. Собственная граница строки — её собственный префикс, совпадающий с её суффиксом. Наибольшая собственная граница префикса образца длины k обозначается через p[k] и есть длина наибольшего собственного префикса этого префикса, совпадающего с его суффиксом. Функция p и есть префикс-функция; на ней стоит поиск Кнута — Морриса — Пратта. Свойство, ради которого префикс-функция и нужна: множество всех границ строки получается повторным применением p, то есть цепочкой p[k], p[p[k]], … до нуля. Оно позволяет при несовпадении сдвигать образец не на один символ, а сразу на длину, потерянную границей. Z-функция строки: z[i] есть длина наибольшего общего префикса самой строки и её суффикса, начинающегося в позиции i. Значение z[0] по соглашению не определено либо полагается равным длине строки; изложение выбирает второе и говорит об этом. Z-блок — отрезок [l, r), являющийся префиксом строки и обнаруженный ранее. Пара (l, r) есть состояние вычисления Z-функции, и именно повторное использование уже известного блока даёт линейность. Хеш строки в описании Рабина — Карпа есть значение многочлена от кодов символов по фиксированному основанию, взятое по модулю. Скользящий пересчёт хеша окна — вычитание вклада ушедшего символа, умножение на основание и прибавление вклада вошедшего. Бор множества образцов — дерево, рёбра которого помечены символами, а пути от корня суть префиксы образцов. Суффиксная ссылка узла ведёт в узел, отвечающий наибольшему собственному суффиксу его строки, который также является узлом бора; конечная ссылка ведёт в ближайший по суффиксным ссылкам узел, отвечающий целому образцу.

Referencing norms: AnswersHere, f-001e2448ea923aa231b0ceeb, f-00b0c7c56b1db3cb52e13999, f-01baaddf11a72b20d24fd78b, f-10c3347d60c1f370afc1b707, f-148e5b7df187d900f17a9809, f-160722885e36b1529bbcafae, f-190a0026278201eb32fff2cc, f-1f4602e4e8f7cfb6b6c1762c, f-200c6ea5581d289983ab0661, f-22877fb4270c36a01eaadbfc, f-2994e8c11849d4822571ea70, f-2bde48ac1fa06f7edc5a48ea, f-2ddbc2e1b865815754678da8, f-2ddf1cfc5a1ff1b4420cc832, f-303b8a15d8ef6033c54c07b3, f-31c170842351086a75c85277, f-31d738ef90ae0858f9818e80, f-340007793f6159d6c69797be, f-39718ec6ffebe257f10a8968, f-3a3027a1c44a9bbb908e951b, f-3d0956263c4311f6d080d13c, f-42ebbb34f3962e67429fc18d, f-45e9c5947ac84d202d5c9051, f-4bc0b00244e11ba3edb15756, f-4ca6435beb8d7dc3c9f90fe3, f-4f1378708e4dc92384bee6f1, f-57aa14b7df9bb45aa6e575d5, f-69f86138460b704821842bd8, f-72a0f69b52ad19796610fcdb, f-768074fe1a7b4fa7d887f649, f-804b3fa6c9abd07ccd6db908, f-8117a7e6d2211de7723483b4, f-8ade40ffef587a0cd99fd2d4, f-91cafe422029388c7e9aae56, f-b4f08d94681e1a9b669f473c, f-c312a977623f87c75af1902f, f-c59483bdb0c22561f2444b2d, f-c70724c1ea04588dc9c100d0, f-ccfa6a8f5b44e8f62052bd43, f-dd3b1f442f960a41f0cbfcca, f-e52c557942b060aea732e336, f-f5f83ffcd30c2592ebc1bfab, f-f6181ab828b74a0a8549d3fe, f-fbd71546a49d3934ac5d1cc6

ru · official · sha256:c329ccc4cd75a4e4e62136bf924553654dc74eaf9389016f467652aa64db4ac5RU

§2. Наивный поиск подстроки Задача: найти все вхождения образца в текст. Вариант — перебор всех начальных позиций с посимвольным сравнением, без предварительной обработки образца. Начальная позиция пробегает значения от нуля до n − m включительно. Для каждой позиции символы образца сравниваются с символами текста слева направо; при полном совпадении позиция объявляется вхождением, при первом расхождении сравнение прекращается и начальная позиция увеличивается на единицу. Основание корректности — определение вхождения §1: описание проверяет его буквально, ничего не предполагая о структуре образца. Инвариант: перед проверкой позиции i все меньшие позиции проверены и объявлены вхождениями ровно тогда, когда ими являются. Худший случай — образец и текст из одинаковых символов с расхождением в последнем: порядка n·m сравнений. Ни одна работа между попытками не переносится, и именно это устраняют §3 и §4. Крайние случаи: пустой образец — вхождением является всякая позиция от нуля до n включительно, и этот случай надо называть; образец длиннее текста — вхождений нет, и цикл не выполняется ни разу.

Referencing norms: f-01503b67e46f867db94f98ff, f-0841edf74f6255b12125a893, f-0b25809f91fb0ddc6c237d13, f-119dc7050b5da1598686e7af, f-149aef6002d364ae17a2b06b, f-1e2886faa8f81d72f01331ec, f-207afd4a10e7f45358eae52a, f-20bbafbdbf0517ec335c43b3, f-20cba30a8bbe769d3578c240, f-21f80eab18c7078951305449, f-256c3d47fbc8e036065e3383, f-27d570361b9f51fcab207ed2, f-2c12f94f5b965cc488bb8dae, f-2c4068a4fded6be8a77de595, f-2df6d9cd8b50bc979ac53697, f-2ea2a9d3927ec0440077d0af, f-305b6fcc1ec4fefd97eadeed, f-31d5388f083d426bdec9da3b, f-36eb934bd98a64a6c1205a99, f-3a3725aae882f1031d2c8bf5, f-3da6eeaf1585bac1a031c7d1, f-4288fd839482f35818daf971, f-43e88577030bea839d080f91, f-44d50b3c8fb205c3ed43dacd, f-47ca3e7b8f39a31c503c0fca, f-4b613fe7a58ec7c18eb843bf, f-4d2e7a781df5626624b924a2, f-55cdb7f5f95d3a333332e561, f-58ee66f4a7331d72a83127fb, f-5ae6391efa9c3429505c74e9, f-5d4e06ae5a73d4f69be55fc6, f-5deade896a1c5110636a1db6, f-5f0200dcd3915fbd8db3221f, f-626e3dfdfdb8da3e649ffe0d, f-672d92ad5d4c688f72ddfebb, f-6979ebbeac967118f8e9d1ab, f-7334aaef7a20f2f811f7f9d4, f-7bde2fdbfbff3d8d9bc26939, f-7d739e72a9e6841288119785, f-7daa33653536c4b878612525, f-7f335567053848582e723853, f-852a3bc176244eaa0aa4a03c, f-88cf92e2e8b51e8c8437b238, f-88e0cfdb0b35512d5a89aff1, f-89df7b8bce9ed7c153930b07, f-89fd2e53d129da956f91c96e, f-972c35b70cce5cf38e8b1bd9, f-9b5a0b23eb0c17b6c483d63b, f-a1c74f5093662a8f8b1df740, f-a56f24bd693de60f5e29027f, f-a8cfbdc75f2fe06733c1ee15, f-a9b506fbeca9fdcbaeb43b20, f-ac55cc72bf25452854cddefa, f-acf865553ba37aad93475240, f-af9d349a7b82fb2756a21848, f-b6f8174b6435111330b166ed, f-b7240bcbbc7820931b5ff05b, f-bc38e0f5657abc7626a0caaa, f-beb8204a084eee64869dd0d5, f-bf69ba02ef0950573d92c92b, f-c0f1e9dc568e9725b9185423, f-c246c7c57da9df4f838823cd, f-c2704dbcb599fdc8d0ded7db, f-c3517801d1bbf1bc4915c795, f-c473464a0d2edb771c9a879c, f-c703fe4a2e956e696a57fc92, f-c7c7eddcb25350a3310d7bec, f-cc37739ee04fe4a4ee0d874b, f-d17ec272463cf48dd9098c45, f-d2ad701028f1532d21a6b59d, f-d35baf67f4b77c73ae1d2d16, f-d3d0c0595ce4a37e8fef1d25, f-d5d54cf3423761384115d68c, f-d64b556b6fe6882dc1d24a91, f-d8a2d157530663c1bae934da, f-d9ffe120e7fd613bc637c6cd, f-dbce0e678c743a4cf18d2206, f-dfdb9abe0d79d9d117f4b188, f-e3df3013f0a1c526922904f7, f-e4bfec888f5a87355a97eeea, f-e561772cd6c958a515b6df50, f-eeafe93016bfbfafa3a1f34a, f-f626141afd4e819ecf33ab74, f-f7f29b3b6463e48d51a144bf, f-f87d67b81859e749c6985297, f-fa47f74e5410f0c9a10e53ac, f-fbc1ef44343d0d7701c36391, f-fbeed0443ac9937b266c6e6b, f-fc87c7fc776b7e3520b9ce25, f-fcea8ef199d46731bfbcf4b3

ru · official · sha256:1c5caebaeabaa3f2e4d038db426a51e1cf4e2aacbdc9bec80711dfb36ca465c1RU

§3. Поиск Кнута — Морриса — Пратта Задача та же. Вариант — с предварительным вычислением префикс-функции образца и одним проходом по тексту без возвратов. Сначала вычисляется префикс-функция образца: для каждого k от единицы до m − 1 длина наибольшей собственной границы префикса длины k + 1. Вычисление ведётся тем же приёмом, что и сам поиск: кандидатная длина уменьшается по цепочке границ, пока символы не совпадут либо длина не станет нулём. Затем текст проходится один раз; поддерживается длина текущего совпавшего префикса образца. При несовпадении длина уменьшается по цепочке границ, при совпадении увеличивается на единицу; при достижении m объявляется вхождение, и длина уменьшается до p[m − 1]. Указатель текста НИКОГДА не убывает — это главное свойство варианта и причина линейности. Общее число уменьшений длины не превосходит числа её увеличений, а последних не более n; отсюда линейность суммарно, а не пошагово. Основание сдвига: при несовпадении после k совпавших символов образец можно сдвинуть так, чтобы совпал наибольший собственный суффикс совпавшей части, являющийся её префиксом. Пропуск меньших сдвигов допустим потому, что при них совпадения быть не может — это и есть содержание префикс-функции. Крайние случаи: пустой образец обрабатывается отдельно; образец из одинаковых символов даёт префикс-функцию 0, 1, 2, …, и сдвиг всегда единичный. Оценка: предварительная обработка порядка m, поиск порядка n, память порядка m. Обе оценки принадлежат источнику вместе с доказательством амортизации.

Referencing norms: f-0150cf82cbf5a8b29417f6e8, f-04949f331555cb3924cfc943, f-06f76acb1d11709ce5513d16, f-08f0f8f035c9964ff1a19d4e, f-0a5945d5f8589779abc6f8eb, f-0c51fca71c3e95a326a970aa, f-1071626e5db52878897ab683, f-11043e031965242699726c7c, f-1179050e3b55598e409b7947, f-188edd955d54ed21a95093d7, f-197c977792a16dbe05570eef, f-19c03a4ccf177fa8f12db00c, f-20539159e5c61892b9c47038, f-213429b4540cef0a2acd9788, f-217107e3638391aa75d7c2dc, f-219f1e7bdb81e709e9a7cd1c, f-228111c97047bf4a1101bc64, f-2296f02e70641d4be63d36f1, f-2349254c9a9285f3888f93c2, f-2669970dcb60530f652177c1, f-279dfb3990a81cd41b948704, f-28a4567c5f9db83692b0baa2, f-2f42ff220e93a1c525b3ba1c, f-32cf4adfd14ba7e05277a796, f-3544758d3657dfe5366e5289, f-35b4ed1356ce9795e29d1110, f-36db187164c9a4bc6619fa64, f-386cd65da80a672d4a028a44, f-3b007fc43c9e19e098f7a9da, f-3bd15d9163857faf6e185616, f-410671f1342583ad395085c9, f-41ad15d09cef1a07bf132054, f-437af8b19bd2432d0c923975, f-4380c156bebac579db751f81, f-45ca8b4a888ddc5a98bb23d8, f-49831c1341b05f8d0ac901cf, f-4dca85e86056093a12562eb3, f-4de89a5064d46984d27469d2, f-51b8dc5184f43bd33eb1f448, f-553882a377171143a6a6e337, f-5748f37c5c8ce811eca73a9d, f-57b1fae74f28ed45f266c3d0, f-58a7dceb49b5d32c4860523f, f-5dea7f1630337d4076769983, f-6259ef5c77dfd4e4ddde3209, f-672bf95c05140167b5e130a4, f-701c4d652fb1995bff19b6f5, f-71dc542b1455c4d5efccd262, f-73c2b55806f7d905953fa57b, f-7445755bdbfd7ea940cf9bef, f-75f4f9b4c154a6d7e15c9b36, f-77e39b44e21ae0f48e91dd9c, f-7c52720d2c2a6c321186f5ca, f-83d4fa50288ccfb35e78ed8b, f-8d2f6d4f36d01d48db637f5d, f-8e7c168daf065c2dd6a8fff1, f-92713aabd9ccb239c25f7bd3, f-9307ac38e64b195c3450b8a2, f-9a244ea749aed6918a36ab3c, f-9c121b7c58b1666ce7d2d24d, f-a1dc713e3af9fa0412969cc2, f-a2611deb4e57631013b135a1, f-a29e33c6bf6cbdbe5b6f62b7, f-a2b9822f902db6137b9db662, f-a75b7bb97712d7558abde349, f-a88227e2348d2be0201559e9, f-a94101e822c7c3921c729c65, f-aff2f46a68af715875e66971, f-b56851369537350fde36e74c, f-b7f359195306c97df9c99245, f-b96da7e2a365cd21077ad43b, f-bbe39bfff1f34688b5d2f58f, f-bebc3728732e333b553f76a8, f-c09230af74c15f28a911dbae, f-c38811d33d8963b6d4752c75, f-c4afadf0cb2eef65dcfbad12, f-c549602c2f6f4b14386a195d, f-c6a4748bafd0dc247a9b51cc, f-c9ba017d1dc55951b9b716cb, f-cb795622b23d9f0e388207f3, f-cee4fb58b39ffdabae202509, f-d2a89708ecb793e2fc0b6e98, f-d35a5e22ef8921c901dc6639, f-d39abfd54a6e8cf26ab87288, f-d782dc227b213527dac11614, f-d83d5fa5ff58cb75f4ff2824, f-d94bef9bb8e5655c1188deae, f-db24962d8a134b6687dc92df, f-dbe42b0e3baea2359f7c6b6f, f-dd1e9c847542626da4ba879f, f-e1430aac6e0df18fd8cb2788, f-e1c4248c73ececa95d3a5361, f-e323656824666db402c805b4, f-e3454feeef8c59e8e26b64df, f-e3fc5c9fb5c8be3a9b446499, f-e43089078ca21272ea60b451, f-e4384dc7522175f08fe720b8, f-e4459bb323444ac116f4d208, f-e479d8f0a4dc23e2a1b23d35, f-ea1143f2b25bb74caccc1d3c, f-ed44adf319ddbc0ffbe14065, f-ef2aab81739ecadfd041b373, f-ef3cf0c4f1512fe1811f6a93, f-f13901e2ab7e6f1e839e37f1, f-f3a1e89818bdc3b701209b28, f-f4c6a75c29811f4f53caee3e, f-f532d84049ab79ee5b95a898, f-f6b626ba5974aaefd3cd72c5, f-f8e4381c0b1198cbbe78aed7, f-f9f11dcd0f5bbb4f4b5d5671, f-fb0d4b9f78299c1f41d362d9

ru · official · sha256:b2edc48fe3144da35e077bcb4d2e8311dd88edba9666a91b67b8c3ef3ce55120RU

§4. Z-функция Задача: по строке получить массив z, в котором z[i] есть длина наибольшего общего префикса строки и её суффикса с позиции i. Вариант — с поддержкой самого правого известного Z-блока. Поддерживается пара (l, r) — границы самого правого обнаруженного блока, являющегося префиксом строки. Для очередной позиции i, если i меньше r, начальное значение z[i] берётся как минимум из r − i и z[i − l]: внутри блока строка повторяет свой префикс, и уже вычисленное значение переносится. Затем значение увеличивается посимвольным сравнением, и при выходе за r блок обновляется. Основание переноса — равенство подстроки [l, r) префиксу строки: позиция i внутри блока отвечает позиции i − l от начала префикса, поэтому известное z[i − l] применимо. Ограничение минимумом с r − i обязательно: за пределами блока равенство не гарантировано, и без ограничения описание неверно. Инвариант: перед обработкой позиции i значения z для всех меньших позиций верны, а (l, r) есть самый правый обнаруженный блок среди них. Линейность: указатель r не убывает, а каждое посимвольное сравнение либо увеличивает r, либо завершает обработку позиции. Отсюда суммарно не более 2n сравнений. Применение: поиск подстроки сводится к Z-функции строки «образец, разделитель, текст»; позиции со значением, равным m, суть вхождения. Разделитель обязан не встречаться ни в образце, ни в тексте, иначе сведение неверно.

Referencing norms: f-055e68bc96f54e56537612e5, f-090b1182110d878aff4dcebe, f-0b5464de6c94222497666220, f-0d42b4e107e11a0d187eade1, f-0e85653dc890866be9734892, f-101da7f76ee49c8dd216427f, f-10f37b671c8d2a46ca9395a3, f-111bf01c7c961195d5231982, f-18dcfe04180a79c23c7064ec, f-1d9d5967943e719c51ab571b, f-2018a7a359aae8cbf09cb4e4, f-23f39893426557cd8f41aaf8, f-25c500492d9be07d9f33ac91, f-286d7b77390d89c44b318add, f-29199a1e5a5a8197df82b30a, f-2f54a6a6b1d6e72a144d13d4, f-2f81fca50bcf48eaf16ba484, f-323364fa522375453e17389f, f-3363f178f639529e304d69d9, f-38076363f4c4d5f64a2defd5, f-3a84bb6590ddcbfe823bbc1a, f-3bfa0219ba9978b36c3c5b62, f-42073569d99dc3f6f2e097f7, f-455bc1d4f88a7bd509c636ef, f-495e57254c5430cdc13ff00c, f-4d233551282c5ac2b33fd721, f-4d7683b8e9fa4f176e08c872, f-4f89c6fcb8a6ba8547ad68bd, f-4fad94d6062f40864440c7d5, f-541d2a2b90e9f12dd8aaa5f7, f-54f410f877efc6f0b8f80f48, f-5baa30be0b604429d9812bf4, f-5bef1e1973d07284a6a6fc56, f-5bf41b43a22416ac5fdc7748, f-5c2b720856931c3a18019c71, f-61ac236a99d46dfe6b1750f1, f-65a7365cd66b35b3252f6d22, f-66861c716437a2565d2aa03a, f-6827bf28674cd7dbcbd74235, f-68be000ab0cc4db0413e59cd, f-6acef742563d2c17b1797f16, f-6eafbcfcb05b6cb4c68fbc2d, f-70ea07973e52a67828911554, f-7361eb28decc40ec7582f8de, f-77d7ed39609c154696f5ea36, f-79639709d734b6f9527374a0, f-7d52c68ed596aa2e762bb07d, f-7ff722c51685dbaa39aac8a5, f-808f1223bbca33badea2d083, f-81300c3ed8306c064f15bec4, f-86fe534a8b655672bab0bb39, f-8e1da58eb9fe34439c9dda1e, f-8e24616c7dd35fc8e321d125, f-9193a90e2f666d8fb092855c, f-93674e2693154852260cfc49, f-93d583374b1ad91de23cbd2c, f-94acadcb2034a45fb1222015, f-9688286438a95251cd80b912, f-9909d7837357a5e9c2ba41a5, f-9b9b9b6d82b04c7074758a23, f-9e3691a954b274ca2f647ea7, f-a014aff518eb8619349fde3c, f-a39d51460dc5d49974eb6189, f-a6fed64af667f219e18e21de, f-aa9d0f40a83100a239822e42, f-aad351a6ef1108c11646fde2, f-b2c04e1ce2baf37b76b8ed2d, f-b9181e2617811e3b08af0cdc, f-be4c4fe45186ed5435f27c68, f-c15cb1c5f9c734925dfc3f31, f-c221cced65bcfa24b2940d24, f-c6ebf03a251e6163d45c6018, f-c7535a6553aa3f1328c8bfe6, f-c772ac60625bf2f8772a81a6, f-cdc26772b2fa2d1c3b734773, f-cdea055da31750dba81428e6, f-d02bf490991a457bcd8dfca9, f-d0b00b7ea74e647f5a0cdcd9, f-d18271e431789ff6da35f3c6, f-d34fac8ca2e116240f3e85aa, f-dab4f2315d8fe55f6f33e890, f-dac6069aaa103c5412bba24d, f-de568ea1c252c8539814ce25, f-de8cef2e8ae0b9138df2eaf1, f-df639a8eead4b3fd2f930115, f-e24faed3a91cf5f193a6f21e, f-e3c02476d9b312ecafeaa658, f-e5ac9e3e26fc4ba6d2f4dcac, f-e76adce0327c9939b05e9852, f-edbc80de66bfd8ec8e17d2e5, f-ee9301a10ed6e1d26bfd2e16, f-f14afbb74ec296c3efa5b30f, f-f15aa465099cf4fcc78902ce, f-f8c86b0014cf63ccf965ffb3

ru · official · sha256:3fcbef0b4b90858c1494eeffff8b2ebf4853117b85e1847b993640d4710326c5RU

§5. Поиск Рабина — Карпа Задача та же, что у §2. Вариант — со скользящим полиномиальным хешем окна и обязательной ПРОВЕРКОЙ совпадения при равенстве хешей. Вычисляется хеш образца и хеш первого окна текста длины m. Далее окно сдвигается на одну позицию, и хеш пересчитывается за постоянное время: вычитается вклад ушедшего символа, результат умножается на основание, прибавляется вклад вошедшего. При равенстве хешей выполняется посимвольная проверка. Пропускать её нельзя: равенство хешей не есть равенство строк, и описание без проверки даёт ложные вхождения. Это утверждение — не предостережение, а часть определения варианта. Оценка: ожидаемое время порядка n + m при случайно выбранном модуле и хорошем распределении хешей; худший случай порядка n·m достигается при систематических столкновениях. Оба утверждения принадлежат источнику и предъявляются вместе. Достоинство варианта, ради которого его выбирают: он естественно обобщается на поиск НЕСКОЛЬКИХ образцов одной длины и на двумерный поиск, где хеш строки-окна пересчитывается тем же приёмом. Крайние случаи: переполнение при пересчёте — причина взятия хеша по модулю; отрицательный промежуточный результат при вычитании вклада приводится по модулю обратно.

Referencing norms: f-000f9c6e57d89c8176d17f37, f-011e06d8056413c4cd152f06, f-0543a2126f76c1373cee8290, f-061adbcd1248a997e9c5ed7e, f-099f73dcdb1e3bea8b1ac297, f-0a9e2a1ba52c9f4379fd547c, f-131ca513a2e60fa1d03fd4e7, f-14406eb660b8a03af806d672, f-173329088d5bce1f3d80a542, f-174f4d99764af1d4edbe79c5, f-18f73e868fd33b78818e9023, f-193e3038b23e89f6e377052e, f-1c9eddc5d243c7c955d76492, f-1d09e56574c0240ac3feccd5, f-1fbbdfcfb8ceef8ca7a78c5c, f-201af28b597f1cbb76692cfc, f-2235c98e5d5f09c499d3d6c2, f-2492b2597bb806e3091c649c, f-25617c831b788ede9b1255c2, f-26ded39ddf8965e0a5d32349, f-2b0866a63ca840feede23fa1, f-2be7537d4334d58a2c33bcd8, f-2f006e236023ac118367cfe5, f-2f0162a219d48cb7860ad8ae, f-3625f1828d0f04a5fd15c797, f-3702e9aaed46005a8c72f4a7, f-376460c49440bb0b322c477b, f-469d73c81f006ad81a2211d1, f-48d660ff880959b4fb46e999, f-4991ac1f7534cd41f2c040db, f-4e1ca453a1f341f6d4651133, f-500dc06b614d9d05b6d4729f, f-50e4355814e63cd9646c9081, f-52dec1e7701d3adb20b38e67, f-56b9125aecb6910105741c89, f-5719eac391ab2a144726cd44, f-59cf952a3c16dc10d4b98983, f-5de6155776469788a44a03d4, f-5f6d2b24198e03d36c2327f0, f-638bf765fea603956eb0e362, f-68128c6f68150e9313a70a8b, f-6b5bb494018847b9b759f931, f-6b70cefa9f70964815b6d8b8, f-70ad5f050830ae8f982113c6, f-710848af8c0e3d8b9608c5db, f-71f6f3d8ca48da23f81ed7a9, f-72eca33d4719ea39a6e18260, f-776257dc2067e0d1bf14cf5b, f-7f501cbded4a933ad0dc6130, f-83162e38dc3a4431a8bc9cfe, f-849638f06301cfc088d4b080, f-84d0bb7ced551204b24eb548, f-8964c603355d872faa84eb67, f-8cb6929090160886f9313335, f-8e16a63531d2d9b46384aa98, f-8e7baf4fda20696962921236, f-95c23306a041c6b5b5a65f82, f-96f68b5c12645084f74554e5, f-98c168bef7d7ee736282c833, f-9faabc24362b1124d6508bb4, f-a4c05218ef31852b93919765, f-a734b3ee62f851c043961124, f-a795917637e40e8ce635f1ad, f-a98a1e7adb2620057de9892e, f-aad45c5f009796a5b9b0ebfa, f-ac2d73edcab44c37aeae60ed, f-af5dc40651e01f74f78f75a4, f-b5151564d8a9af3eb2eb020e, f-b718d56e3c1625064da635b8, f-b7f157512db8da8b25317a5e, f-bce177bfc4e046be9fe0a530, f-bd2a65cc2532f6ad5869882a, f-bd465cef2377ad09085411c3, f-bd953fe8c23362625eda2129, f-be4f709352ccb713a9f413a9, f-beb243d633fe88df38bde2f0, f-c9ad0325730d0796d407ffac, f-cad5547684e12b447ebb8da0, f-cdd980363835f490ba7ef79e, f-cebcb0b6e57f85ce52207398, f-cf56a98026dd26368ae93fe9, f-d13458abf65d6cf4678e8e2e, f-d3574bf65707cba6e1698c9b, f-d79b4e2f98956711807b41f0, f-d92de758bdf75eb1eadef210, f-d9a26ac74d3d3bc7f3b31355, f-db8c63f2b67b5e826244e9a5, f-db9a02cc303234920aeb28a7, f-dd5541bed924cd3c2a96e04b, f-dd9bf46abe74c5e9ff6bdc4a, f-e0607875621fe40ab2c07470, f-e6a51c454ab3001d0ad0b5b6, f-e82f376cdf92f18e8116f0fe, f-ea781b1779ee8badf3f98a59, f-ea9ae4621e62e90ac856f20b, f-f0f83b9a478b1080982dbd9a, f-f3bd45e1eab24eadfc7c3651, f-f464b1f7d39cc4ef69206ca9, f-f5075f782b6c657bc41ae18f, f-fecab4ecc0d443ce46d2e06f, f-ff2270c1bca823bcb0e06b92, f-ff754f62c0738bf497cf73f2

ru · official · sha256:7e9cc853fb0635da2c90bbbcafdcc49cf1cb2fec389a1fae265349e5d95a80faRU

§6. Поиск множества образцов алгоритмом Ахо — Корасик Задача: найти все вхождения ВСЕХ образцов из данного множества в текст за один проход. Вариант — бор с суффиксными и конечными ссылками, обход текста без возвратов. Сначала строится бор всех образцов. Затем обходом в ширину вычисляются суффиксные ссылки: ссылка корня и его детей ведёт в корень; для узла, полученного из узла u по символу c, ссылка есть переход по c из узла, на который ссылается u, а при отсутствии такого перехода — переход из узла по цепочке ссылок дальше. Одновременно вычисляются конечные ссылки: ближайший по цепочке суффиксных ссылок узел, отвечающий целому образцу. Затем текст проходится один раз; поддерживается текущий узел бора. По очередному символу выполняется переход; при его отсутствии текущий узел заменяется узлом по суффиксной ссылке, и попытка повторяется до корня. В каждом достигнутом узле выдаются все образцы, найденные обходом по конечным ссылкам. Порядок обхода в ширину при построении ссылок существен: ссылка узла глубины k опирается на ссылки узлов меньшей глубины, и обход в глубину дал бы неверные значения. Это самая частая ошибка изложений. Конечные ссылки нужны для того, чтобы не терять КОРОТКИЕ образцы, являющиеся суффиксами длинных: без них вхождение образца «he» внутри «she» не будет выдано. Оценка: построение бора порядка суммарной длины образцов, вычисление ссылок того же порядка, проход по тексту порядка n плюс число найденных вхождений. Последнее слагаемое неустранимо: вхождений может быть квадратично много. Крайние случаи: множество образцов пусто — бор состоит из корня, и вхождений нет; один образец есть частный случай, и на нём описание совпадает с §3 по существу, отличаясь устройством.

Referencing norms: f-02e37603770690d2d03a5570, f-0320997988875af20253f28f, f-04d0603b06ff87eaa4a1541f, f-096c69d270570c85efaf6eee, f-0ac3464a0cdbfbca674fc6df, f-0ec23c203dfe849e66f77d2e, f-14e176d144e3a2eecc67cb98, f-1a143945e1cd6699e2a1441b, f-1bb0c9f6ea6afd13811a42b6, f-1bc6e67bc68df3f526479dc1, f-1c145edcc70574b18a731d27, f-1cae1559576486212502ead3, f-1d0a58ae5ac20c88c961f968, f-1dbde6cd94a38bd4d48974a8, f-2419adc91d01d6aa2542b742, f-2450e9efa01415c0270b9d12, f-2497624cfee45511003cbe21, f-2ab5aec5bce36ceadaa5f464, f-2e88c30169bb45c1d0e913aa, f-30136af2957a41d38b7ba712, f-345bb58b59cb696d23aa81f9, f-3739cf3a49871ca0b4161e2b, f-38f94b06121068506346e447, f-3df4e8e2c9ea01fce9116bdd, f-442f8c1fc56622a59b612dcb, f-496c8986d4bbb0696b157f10, f-4ef9c75d634d67aadea7e475, f-4faec582955f6ea3adf8f458, f-5745baf3924f4e5b37a0e2b6, f-5bc893f6355c450ea2f18f48, f-5be1ca42907769385f4853be, f-5d8826835bc72d06ea065472, f-5dfaf51583368767a26d0062, f-5e8012bdf5a54985068cf4e6, f-5f22a49eaed35ea476bfa75d, f-60ad8eb74d5ea2e322f1f61f, f-67900200694064baaaf788bc, f-67a2ed21c43518905943f9f3, f-6a1a34c5440cbe387561e010, f-6e7f98e80ed458db12fd4158, f-6ecfd996ea06bb1c8b30bf1a, f-6f0548a82b22e2b83cce538f, f-6fabf512f7914e44c66f986e, f-6fd018c5e9852203fd47596a, f-73173d348fef53ac1c5e1bb4, f-737dd2bbf68e32118b8abe4f, f-739880389fd2f74876877105, f-75e11d0118097a2f1e7080c0, f-767eb54ceffb5096f7f0caf9, f-77bb3ac105cefaf38890e3cc, f-793278425d71a14e8389860c, f-79b559f3bdd07d09cf436d60, f-7adbff279a9698018ba00e94, f-7be68ce9f6aa1e153a226f9e, f-7d44b768807993274d3043dd, f-7ea12821cbb637cdae49e536, f-829e1dd7e5130d5fb2b85a95, f-8376862654058b39f17f0012, f-852109ffb44757ce5e82123f, f-89c8747ebd2d23b3c6bf5e69, f-8a3f2bc22e6e4439d2e24d5f, f-8d2557d0a40787e2392d76b6, f-8d3ed15267d2f69490370596, f-8fd32e720236c001c9509b76, f-904290231e555538bf0b1a80, f-92b931f4d2074ec061834222, f-979d2438691077e62040e465, f-9bb3afaaa94c91e7b789617a, f-9e834581b939ee51da73a19d, f-9f6c3b8bfe7bd3f8fb5e72ca, f-a0441bf1703fc709b52daf94, f-a0728112241e9984bc513fb2, f-a0ce9d6506c18f19e080a538, f-a3d292294b5719482a80521d, f-a4a6c287871d447ac99f1d2b, f-a976a68549df0a43608ed1be, f-ac997a470bae685f75874c6b, f-aeae496558cd8f629bcd580a, f-b199c5834e2cf7e1c1483bbb, f-b30a1fda7bf0bf82e93e660c, f-b914788fb3e4abc94823fc99, f-ba09e17d2969d0542b2e95fe, f-ba2d93db0731723cce208596, f-bd339e8be279f6ab9f8afbdd, f-c1730d610312be9d3fab26e8, f-c315a0b9f008988dc043c6be, f-c7384f7eca87223bcfa704eb, f-c77328f54b42c467c8bd4d85, f-c7b9094f8c258bc14052ad36, f-c857e0f4f32044bdd44177fa, f-c8965c691324e588dcece01f, f-cfff7abb1c9081455e4856ac, f-d36b995144012020983ff6e3, f-d4c17a8873bf6df44a17f44a, f-d96d101ea584100ff539b3c5, f-dc4d9ce51b6614e8158e5904, f-de3d0e07eb69915262336263, f-de66df90c39c477595d60b67, f-de9aab84b67b74f4658f16cd, f-e197acef40d6a0cc5c283464, f-e2359d40067ebcdddd77683d, f-e3b5ff1b13f9df648238a46b, f-e6e57c6a7ecaf3e153364b9b, f-f0600876028785f92efd3c57, f-f30ef7a491d9c4dfff6473bb, f-f6a4fa8b77e6ae53fb9b41b5, f-f6cb6f7a06adaafd7cc6f44e, f-fb6e1241c5b49faa18e8c461, f-fca21681547bde0492b96f5b

ru · official · sha256:5f2118d20e7b5d598e2e91e27648d840d259846e8b15a740433b597a1ae3e34bRU

СТРОКОВЫЕ АЛГОРИТМЫ: НАИВНЫЙ ПОИСК, КНУТ — МОРРИС — ПРАТТ, Z-ФУНКЦИЯ, РАБИН — КАРП И АХО — КОРАСИК Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство пяти алгоритмов над строками: наивного поиска подстроки, поиска Кнута — Морриса — Пратта, вычисления Z-функции, поиска Рабина — Карпа и поиска множества образцов алгоритмом Ахо — Корасик. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна строка здесь не просматривается.