Статья :
Алгоритмы поиска в тексте

Автор(ы): Андрей Боровский
Дата: 28.01.2002

Авторы :
Андрей Боровский

Блоьшое спасибо за ценную информацию.
Мне как раз нужно поиск в тексте реализовывыть —
вы мне очень помогли.
Редко встретишь в инете толковую статью —
ваша как раз такая. Еще раз спасибо.

В статье неверно (точнее, неоптимально) описан следующий момент. В том случае, если при поиске "неусложненным" методом Бойера-Мура несовпадение встречается не на последнем символе образца, автор предлагает сдвигать образец вправо на 1 позицию, как в этом примере:

a b e c c a c b a d b a b b a d
          a b b a d

Между тем, совершенно очевидно, что т.к. символ c не встречается в образце, то можно сдвинуть образец на две позиции:

a b e c c a c b a d b a b b a d
              a b b a d

Строго говоря, если несовпадение обнаружилось на k-м справа символе образца, его нужно сдвинуть вправо на BMT[c] — k + 1 позиций, где c — символ из строки, не совпавший с символом из образца.

строки в текст.
Как это сделать, креме как тупым поиском?

а кстати... http://alglib.manual.ru/searching/bmh.php

Здравствуйте, PK Sly, Вы писали:

PS>Как это сделать, креме как тупым поиском?
переверни строку и ищи с конца любым алгоритмом

PS>>Как это сделать, креме как тупым поиском?
C>переверни строку и ищи с конца любым алгоритмом

Ну, во-первых, переворачивать не обязательно, можно искать, начиная с конца и заполняя BMT таблицу "обратным" образом.
А во-вторых, описанный алгоритм предназначен для поиска именно сторки целиком, для чего и строится эта таблица. Очень легко представть себе случаи, когда этот алгоритм пропустит подстроку всего лишь на один символ короче.

PS>Ну, во-первых, переворачивать не обязательно, можно искать, начиная с конца и заполняя BMT таблицу "обратным" образом.
PS>А во-вторых, описанный алгоритм предназначен для поиска именно сторки целиком, для чего и строится эта таблица.

PS>Очень легко представть себе случаи, когда этот алгоритм пропустит подстроку всего лишь на один символ короче.

Не вполне понял: предложеный алгоритм неверный? неоптимальный?
Если перевернуть строку и искать с конца будет найдено первое вхождение перевернутой строки в перевернутый текст. Это будет самое последнее вхождение исходной строки строки в исходный текст. Если это неверно, проссьба привести пример.

C>Не вполне понял: предложеный алгоритм неверный? неоптимальный?
C>Если перевернуть строку и искать с конца будет найдено первое вхождение перевернутой строки в перевернутый текст. Это будет самое последнее вхождение исходной строки строки в исходный текст. Если это неверно, проссьба привести пример.

Надо найти не последнее вхождение, а максимальное.
То есть, подстрока максимальной длины, начитая с начала.

Здравствуйте, PK Sly, Вы писали:

PS>Надо найти не последнее вхождение, а максимальное.
PS>То есть, подстрока максимальной длины, начитая с начала.
я неправильно понял условие.
подстрока удовлетворяет какому-либо условию еще? Если можно, с примером.

например, текст такой:

qwerkqwhgvoiuqwertyusdmnbbpcdsuy

подстрока, которую ищем такая:

qwertyuiop

частичные вхождения строки выделены курсивом, а максимальное вхождение — жирным

qwerkqwhgvoiuqwertyusdmnbbpcdsuy

Здравствуйте, PK Sly, Вы писали:


PS>частичные вхождения строки выделены курсивом, а максимальное вхождение — жирным

PS>qwerkqwhgvoiuqwertyusdmnbbpcdsuy

а... максимальное вхождение подстроки исходной строки в текст...

можно построить, например, конечный автомат для поиска искомой строки, потом пройтись этим автоматом по входному тексту и найти самую удаленную от стартовой вершину, в которую автомат попаедет при прохождении по тексту. Этой вершине будет соответствовать путь от начальной, которому будет соответстовать самый длинный префикс строки.

Здравствуйте, Alexander Fenster, Вы писали:

AF>В статье неверно (точнее, неоптимально) описан следующий момент....

Так все-таки "неверно" или "неоптимально"? Это ведь принципиально разные понятия.
Я взял простейший вариант БМ, со сдвигом на один символ, такой вариант, кстати,
описан в литературе, как и несколько других, на один из которых Вы сослались. Все это нкжно было чтобы по контрасту показать преимущества более оптимального, усложненного алгоритма, который и описывается дальше.
С уважением,
А. Боровский.

C>а... максимальное вхождение подстроки исходной строки в текст...

не любой подстроки, а только начиная с начала

C>можно построить, например, конечный автомат для поиска искомой строки, потом пройтись этим автоматом по входному тексту и найти самую удаленную от стартовой вершину, в которую автомат попаедет при прохождении по тексту. Этой вершине будет соответствовать путь от начальной, которому будет соответстовать самый длинный префикс строки.

ууууу... дааа.. это называется горе от ума
тупой поиск делается гораздо проще. через memchr и memcmp

Здравствуйте, PK Sly, Вы писали:

PS>не любой подстроки, а только начиная с начала
да, это он и есть. Просто неточно написал
PS>ууууу... дааа.. это называется горе от ума
PS>тупой поиск делается гораздо проще. через memchr и memcmp
Никто не говорил, что будет легко
Этот вариант — более оптимальный, чем memcmp (один раз строим автомат, один раз про ходим по строке, один раз ищем результат). Если важна простота реализации — конечно лучше memcmp %)

C>Никто не говорил, что будет легко
C>Этот вариант — более оптимальный, чем memcmp (один раз строим автомат, один раз про ходим по строке, один раз ищем результат). Если важна простота реализации — конечно лучше memcmp %)

поспорим что memchr + memcmp будет быстрее, чем автомат?

Здравствуйте, PK Sly, Вы писали:

PS>поспорим что memchr + memcmp будет быстрее, чем автомат?
Спорить не буду, потому что не знаю специфики входных данных.
Автомат быстрее, чем memchr + memcmp, на длинных текстах (если memchr + memcmp будут использоваться самым простым методом: перебором всех смещений в тексте по очереди и нахождение длины префикса искомой строки, совпадающего при смещении)

например, если текст это

qweqweqweqwe...[big]...qwerty

а строка — qwerty
то в моем понимании, тупое использование memcmp + memchr будет обрабатывать символы примерно так:

qwe
w
e
qwe
w
e
...
qwerty
w
e
r
t
y

Есил строки для поиска маленькие и их много, то конечно большая часть времени будет уходить на построение автомата
если строка одна и текстов много или текст длинный — автомат быстрее
Если строка по длине сравнима с текстом — вот тут

PS>>поспорим что memchr + memcmp будет быстрее, чем автомат?
C>Спорить не буду, потому что не знаю специфики входных данных.

данные — обычный текст. любой. текстовый
HTML, XML, plain text или что угодно

C>Автомат быстрее, чем memchr + memcmp, на длинных текстах (если memchr + memcmp будут использоваться самым простым методом: перебором всех смещений в тексте по очереди и нахождение длины префикса искомой строки, совпадающего при смещении)

C>например, если текст это
C>

C>qweqweqweqwe...[big]...qwerty

C>а строка — qwerty
C>то в моем понимании, тупое использование memcmp + memchr будет обрабатывать символы примерно так:

C>

C>qwe
C>w
C>e
C>qwe
C>w
C>e
C>...
C>qwerty
C>w
C>e
C>r
C>t
C>y

ладно. а автомат как быдет тействовать?
Будет делать тоже самое, но на каждую букву ещё лезть в таблицу?

C>Есил строки для поиска маленькие и их много, то конечно большая часть времени будет уходить на построение автомата
C>если строка одна и текстов много или текст длинный — автомат быстрее
C>Если строка по длине сравнима с текстом — вот тут

Да хоть маленькие, хоть большие. Не могу для данной задачи придумать, где тут можно использовать автомат.

Здравствуйте, PK Sly, Вы писали:

PS>данные — обычный текст. любой. текстовый
PS>HTML, XML, plain text или что угодно

PS>автомат как быдет тействовать?
PS>Будет делать тоже самое, но на каждую букву ещё лезть в таблицу?
автомат для каждый буквы будет один раз лезть в таблицу (одно обращение к симоблу строки и к таблице) и на основнии символа на входе и текущего состояния, выбирать новое состояние. Таким образом, проход автоматом по любой строке по
времени пропорционально длине строки
Проход по строке с помощью memchr + memcmp так, как он был описан, в некоторых случаях будет по нескольку раз обращаться к одной и той же букве в исходной строке (в том примере — примерно по два раза). Можно сконструировать такие входные тексты, на которых memcmp + memchr будет работать по времени пропорциорционально k * длину строки

непример, строка xxxxxxxxy и тектст
xxxxxxxxxxxxxxxxxxxxxxx...[big]...xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy

C>автомат для каждый буквы будет один раз лезть в таблицу (одно обращение к симоблу строки и к таблице) и на основнии символа на входе и текущего состояния, выбирать новое состояние. Таким образом, проход автоматом по любой строке по
C>времени пропорционально длине строки

если бы одна буква всегда была только в одном вхождении..
а вот как быть автомату с такой строкой:
abcabcabcde и строкой поиска abcde
выделенная буква входит в две подпоследовательности: одна начинается с нулевой позиции, другая — с третьей.

похоже, что одним проходом тут не обойтись.

да и ещё вопрос, как автоматически и за разумное время сгенерить автомат. как бы не оказалось, что это время будет сравнимо с временем поиска

Здравствуйте, PK Sly, Вы писали:

PS>если бы одна буква всегда была только в одном вхождении..
PS>а вот как быть автомату с такой строкой:
PS>abcabcabcde и строкой поиска abcde
PS>выделенная буква входит в две подпоследовательности: одна начинается с нулевой позиции, другая — с третьей.
PS>похоже, что одним проходом тут не обойтись.

можно обойтись. Всегда. Главное построить автомат.
Для этого примера функция переходов будет такой

p(0,a) = 1
p(1,b) = 2
p(2,c) = 3
p(3,d) = 4
p(4,e) = 5

начальное состояние — 0
все остальные переходы — в начальное состояние (т.е. p(2,a) -> 0, p(5,z) -> 0 и т. п.)
пробег автомата по приведенной в примере строке

abcabcabcde
012012012345

Это тривиальный пример. Функция переходов может быть не столь простой, если строка имеет повторяющуюся структуру (например, abcabc). Но скорость прохода по строке в результате не изменится.

PS>да и ещё вопрос, как автоматически и за разумное время сгенерить автомат. как бы не оказалось, что это время
будет сравнимо с временем поиска

про то, как строится автомат, написано, например, в книге "Алгоритмы: простоение и анализ"
там также, говорится, что для строки длины m автомат можно прострить за O(m*E), где E — количество символов в алфавите (в нашем случае — 256), а m — длина образца, и приводится тупой алгоритм, работающий за O(m^3*E), что для небольших строк тоже приемлемо..

C>

C>p(0,a) = 1
C>p(1,b) = 2
C>p(2,c) = 3
C>p(3,d) = 4
C>p(4,e) = 5

C>

C>abcabcabcde
C>012012012345

Опять же, этот автомат, как и ВМТ-таблица, ориентирован на поиск строки ЦЕЛИКОМ. Данный автомат легко может не найти подстроку "ab".

На мой взгляд, задача схожа с wildcard match, где без откатов — ну просто никак не обойтись. И, кстати, интересно, существует ли атомат, решающий эту задачу? Обычная рекурсивная функция занимает 10 строчек, а как сделать автомат, у меня, например, идей нет да и возможно ли это?

C>про то, как строится автомат, написано, например, в книге "Алгоритмы: простоение и анализ"

в электронном виде это книжка где-то есть? В яндексте это словосочетание нигде не встречается.

Здравствуйте, PK Sly, Вы писали:

C>>

C>>p(0,a) = 1
C>>p(1,b) = 2
C>>p(2,c) = 3
C>>p(3,d) = 4
C>>p(4,e) = 5

C>>

C>>abcabcabcde
C>>012012012345

PS>Опять же, этот автомат, как и ВМТ-таблица, ориентирован на поиск строки ЦЕЛИКОМ.

Если Вы внимательно посмотрите на мои предыдущие ответы, то сможете увидеть, как именно предлагается использовать автомат для поиска строки целиком для поиска вхождения префикса этой строки максимально длины. В случае этого примера — максимальное вхождение определяется тем смещением, когда автомат попал в состояние 5 — самое удаленное от начального.
PS>Данный автомат легко может не найти подстроку "ab".
Это неверно. Просьба привести пример. (Если в данном примере текст будет содержать ab и не будет содержать abc, то самым удаленным от начального состоянием будет 2 и подстрока ab будет найдена)

PS>На мой взгляд, задача схожа с wildcard match, где без откатов — ну просто никак не обойтись.
PS>И, кстати, интересно, существует ли атомат, решающий эту задачу? Обычная рекурсивная функция занимает 10 строчек, а как сделать автомат, у меня, например, идей нет да и возможно ли это?
Задача wildcard match как раз и решается с помощью автоматов, без откатов. Собственно, конечные автоматы большей
частью и были придуманы для решения этой задачи

C>>про то, как строится автомат, написано, например, в книге "Алгоритмы: простоение и анализ"
PS>в электронном виде это книжка где-то есть?
Нет, в электронном виде не встречал. Но вообще, наверное, электронных публикаций на эту тему достаточно много. Искать по словам "Префикс-функция" "детерминированные конечные автоматы"

PS>в электронном виде это книжка где-то есть? В яндексте это словосочетание нигде не встречается
Это из-за опечатки и copy-paste, видимо...

Алгоритмы: построение и анализ

PS>>Данный автомат легко может не найти подстроку "ab".
C>Это неверно. Просьба привести пример. (Если в данном примере текст будет содержать ab и не будет содержать abc, то самым удаленным от начального состоянием будет 2 и подстрока ab будет найдена)

а. понял. автомат идёт сначала, а не с конца, как ВМТ.
А как быть сповторяющимися подстроками?

text = "abcabcabcdef", substring = "abcabcdef"
автомат =
(0,a) = 1
(1,b) = 2
(2,c) = 3
(3,a) = 4
(4,b) = 5
(5,c) = 6
(6,d) = 7
(7,e) = 8
(8,f) = 9
(9,*) = exit
(остальное) = 0

тогда проход будет такой:

abcabcabcdef
012345012000

или я неправильно написал автомат?

C>Задача wildcard match как раз и решается с помощью автоматов, без откатов. Собственно, конечные автоматы большей
C>частью и были придуманы для решения этой задачи

интересно посмотреть

C>Нет, в электронном виде не встречал. Но вообще, наверное, электронных публикаций на эту тему достаточно много. Искать по словам "Префикс-функция" "детерминированные конечные автоматы"

спасибо, кое-что нашёл

PS>>в электронном виде это книжка где-то есть? В яндексте это словосочетание нигде не встречается
C>Это из-за опечатки и copy-paste, видимо...

C>

C>Алгоритмы: построение и анализ

очевидно

Здравствуйте, PK Sly, Вы писали:

PS>>>Данный автомат легко может не найти подстроку "ab".
C>>Это неверно. Просьба привести пример. (Если в данном примере текст будет содержать ab и не будет содержать abc, то самым удаленным от начального состоянием будет 2 и подстрока ab будет найдена)

PS>а. понял. автомат идёт сначала, а не с конца, как ВМТ.
PS>А как быть сповторяющимися подстроками?

PS>

PS>text = "abcabcabcdef", substring = "abcabcdef"
PS>или я неправильно написал автомат?

да, неправильно. Нужен еще один переход

[q]
p(0,a) = 1
p(1,b) = 2
p(2,c) = 3
p(3,a) = 4
p(4,b) = 5
p(5,c) = 6
p(6,d) = 7
p(7,e) = 8
p(8,f) = 9

p(5,a) = 3

остальные — в 0

abcabcabcdef
0123453456789

C>>Задача wildcard match как раз и решается с помощью автоматов, без откатов. Собственно, конечные автоматы большей
C>>частью и были придуманы для решения этой задачи
PS>интересно посмотреть
Можно, например, поизучать исходники grep.
Cоответственно поиск по словам "детерминизация", "теория автоматов" "регулярные выражения" "регулярные языки" и т п. Не стоит только путать регулярные выражения, реализованные при помощи недетерминированных конечных автоматов (это аналог перебора, хоть и с кучей оптимизаций — perl, ruby) и детерминированных (grep, sed)

C>

C>p(0,a) = 1
C>p(1,b) = 2
C>p(2,c) = 3
C>p(3,a) = 4
C>p(4,b) = 5
C>p(5,c) = 6
C>p(6,d) = 7
C>p(7,e) = 8
C>p(8,f) = 9

C>p(5,a) = 3

C>остальные — в 0

C>

C>abcabcabcdef
C>0123453456789

состояние (5,a) (выделил жирным) не встречается.
наверное, имелось ввиду

p(6,a) = 4

Тогда работать это будет так:

abcabcabcdef
0123456456789

осталось обобщить это для общего случая

C>Cоответственно поиск по словам "детерминизация", "теория автоматов" "регулярные выражения" "регулярные языки" и т п. Не стоит только путать регулярные выражения, реализованные при помощи недетерминированных конечных автоматов (это аналог перебора, хоть и с кучей оптимизаций — perl, ruby) и детерминированных (grep, sed)

спасибо
хотя, я слышал, что у "ненастоящих" (тех, которые без перебора) регэкспов есть проблемы с определением некоторых комбинаций.

PS>состояние (5,a) (выделил жирным) не встречается.
PS>наверное, имелось ввиду
PS>

PS>p(6,a) = 4

PS>Тогда работать это будет так:
PS>

PS>abcabcabcdef
PS>0123456456789

да, точно.
PS>осталось обобщить это для общего случая
алгорим построения автомата существует и неособенно сложный. Будет время — напишу сюда. Думаю, в инете исходники должны быть.
PS>хотя, я слышал, что у "ненастоящих" (тех, которые без перебора) регэкспов есть проблемы с определением некоторых комбинаций.
grep превосходно ищет по любым регекспам в любых текстах

"Ненастоящие" регекспы не могу принципиально быть использованы для указания обратных ссылок на то место, где текст был найден (для замены или в самом регекспе). Например, всякие перловые конструкции вида

s/(\w+)\s*(\d+)/$2$1/

возможны только с использованием реализации регекспов на НКА. Если же нужен просто поиск с шаблоном (wildcard) — все превосходно реализуется с помощью и детерминированных, и недетерминированных конечных автоматов

PS>>осталось обобщить это для общего случая
C>алгорим построения автомата существует и неособенно сложный. Будет время — напишу сюда. Думаю, в инете исходники должны быть.

тут несколько не то, что требуется в регэкспах или в стандартных ситуациях, так что алгоритм в чистом виде я скорее всего не получу.
главное — дано правильное направление мысли, а значит решение будет
Спасибо!

впрочем, исходникам я тоже обрадуюсь а то в сорцах грепа копаться — довольно муторно..

А>Так все-таки "неверно" или "неоптимально"? Это ведь принципиально разные понятия.

Все-таки "неоптимально", а не "неверно"

(предыдущее — мое)

Здравствуйте, ch00k, Вы писали:

Можно конечно и без конечных автоматов приблизительно так

     Int32 LengthIndexArray, CountIndex;
        Int32 LenOldPattern, LenNewPattern;
        Int32 NewLen;
        char SeachChar, FirstSeachChar;
        Int32 CounEquls;
        Int32 CopyCount, PosOldPatern, IndexInResult, IndexInOrigString;
                 if (OldPattern==null)
                   return;
                  
            LenOldPattern = OldPattern.Length;
             if  (NewPattern==null)
                 LenNewPattern=0;
                 else
            LenNewPattern = NewPattern.Length;
            if  (_len == 0) 
            {
                return;
            }

            char[] OldPatternChar = OldPattern.ToCharArray();
            Int32[] IndexArray = new Int32[16];

            LengthIndexArray = 16;
            CountIndex = 0;
            CounEquls = 0;
            FirstSeachChar = OldPatternChar[0];
            SeachChar = FirstSeachChar;
            char TwoChar = OldPatternChar[1];
        //=======================================================
          //============================================================
            if (LenOldPattern == 1)
            {
                if (LenNewPattern == 1)
                {
                    Replace(FirstSeachChar, NewPattern[1]);
                    return;
                }

                ;
                for (Int32 i = 0; i < _len; i++)
                    if (_buf[i] == FirstSeachChar)
                    {
                        if (CountIndex == LengthIndexArray)
                        {
                            LengthIndexArray = LengthIndexArray * 2;

                            Int32[] TempIndexArray = new Int32[LengthIndexArray];

                            Array.Copy(IndexArray, 0, TempIndexArray, 0, IndexArray.Length);
                            IndexArray = TempIndexArray;
                        }

                        IndexArray[CountIndex] = i;
                        CountIndex++;
                    }
            }
                //========================================================================
                else
            {
                Int32 TwoFirstChar = 0;
                

                for (Int32 i = 1; i < LenOldPattern; i++)
                    if (OldPatternChar[i] == FirstSeachChar)
                    {
                        TwoFirstChar = i;
                        break;
                    }

                //=====================================================================
                if (TwoFirstChar > 0)
                {
                    
                    Int32 ii = 0;

                    while (ii < _len)
                    {
                        if (_buf[ii] == SeachChar)
                        {
                            CounEquls++;
                            if (CounEquls == LenOldPattern)
                            {
                                if (CountIndex == LengthIndexArray)
                                {
                                    LengthIndexArray = LengthIndexArray * 2;

                                    Int32[] TempIndexArray = new Int32[LengthIndexArray];

                                    Array.Copy(IndexArray, 0, TempIndexArray, 0, IndexArray.Length);
                                    IndexArray = TempIndexArray;
                                }

                                IndexArray[CountIndex] = ii - LenOldPattern + 1;
                                CountIndex++;
                                SeachChar = FirstSeachChar;
                                CounEquls = 0;
                            }
                            else
                                SeachChar = OldPatternChar[CounEquls];
                        }
                        else
                        {
                            if (CounEquls > 0)
                            {
                                if (CounEquls >= TwoFirstChar)
                                {
                                    ii = ii - CounEquls + TwoFirstChar + 1;
                                    SeachChar = TwoChar;
                                    CounEquls = 1;
                                    continue;
                                }

                                if (_buf[ii] == FirstSeachChar)
                                {
                                    CounEquls = 1;
                                    SeachChar = OldPattern[1];
                                }
                                else
                                {
                                    SeachChar = FirstSeachChar;
                                    CounEquls = 0;
                                }
                            }
                            //    CounEquls:=0;
                        }

                        ii++;
                    }
                }
                    //=======================================================
                    else
                    for (Int32 i = 0; i < _len; i++)
                    {
                        if (_buf[i] == SeachChar)
                        {
                            CounEquls++;
                            if (CounEquls == LenOldPattern)
                            {
                                if (CountIndex == LengthIndexArray)
                                {
                                    LengthIndexArray = LengthIndexArray * 2;

                                    Int32[] TempIndexArray = new Int32[LengthIndexArray];

                                    Array.Copy(IndexArray, 0, TempIndexArray, 0, IndexArray.Length);
                                    IndexArray = TempIndexArray;
                                }

                                IndexArray[CountIndex] = i - LenOldPattern + 1;
                                CountIndex++;
                                SeachChar = FirstSeachChar;
                                CounEquls = 0;
                            }
                            else
                                SeachChar = OldPatternChar[CounEquls];
                        }
                            //else
                            //{
                            //    SeachChar = FirstSeachChar;
                            //    CounEquls = 0;
                            //}
                            else
                        {
                            if (CounEquls > 0)
                            {
                                if (_buf[i] == FirstSeachChar)
                                {
                                    CounEquls = 1;
                                    SeachChar = TwoChar;
                                }
                                else
                                {
                                    SeachChar = FirstSeachChar;
                                    CounEquls = 0;
                                }
                            }
                            //    CounEquls:=0;
                        }
                    }
            }


            if (CountIndex == 0)
            {
                return;
            }

Мне попалась в руки книга Дэна Гасфилда "Строки, суффиксные деревья и последовательности..."
Там про БМ кое-что более развёрнуто есть.

Алгоритм основан на двух правилах:
— правило плохого символа: если очередной символ не совпал, то нужно сдвинуть "рамку" поиска так, чтобы совместить этот символ с ближайшим вхождением в искомую строку
— правило хорошего суффикса: если совпавший суффикс встречается ещё где-то в искомой строке, сдвинуть рамку, чтобы совместить с ближайшим следующим вхождением
(это лежит в основе алгоритма Кнута-Морриса-Пратта, но из-за простоты воплощения есть смысл скрестить его с

Что здесь есть интересного и нетривиального.

"Плохой символ": самая простая реализация — это для всех символов алфавита найти смещение самого последнего вхождения. Собственно, об этом уже говорилось в статье.
Чем плохо: если символ встречается дважды, то может статься, что сдвигать по правилу надо в обратную сторону!

abcdea -- ищем

...bea.....
abcdea
    ++
   -
  abcdea

  ...aea.....
  abcdea
      ++
     -
abcdea       -- сдвиг по "глупому" правилу
   abcdea    -- дефолт, сдвиг на 1 позицию
     abcdea  -- осмысленный сдвиг

Предложенный в статье подход с таблицей размером N*L где N — длина образца, L — мощность алфавита, разумеется, решает проблему, но весьма дорогой ценой. Для коротких строк (или с малым числом повторяющихся символов) выигрыш между глупым и умным алгоритмами может быть не столь велик, чтобы заморачиваться. А для больших строк — резко возрастает расход памяти и время препроцессинга (заполнения таблицы).

На самом деле, можно сделать некоторые пожертвования — скорость в обмен на память.
Вместо таблицы размером N*L и временем доступа O(1) использовать линейные списки общим размером O(N+L) — для каждого символа — список вхождений в строку, очевидно, в сумме это даст N элементов, плюс оставшиеся не вошедшие; поиск — алгоритм upper_bound, что для списка даст O(N), а для массива — O(log N).
Замечу, что в самом дубовом случае это вырождается в линейный поиск данного символа в строке-образце, от текущей позиции к началу. Это, конечно, жестоко, но можно просто ограничить наши списки вхождений, скажем, не 1 позицией на символ (глупый алгоритм БМ), и не N (мозгожор) — а неким разумным фиксированным количеством — скажем, от 2 до 4.
Если запрос к таблице смещений обломился, то выполним линейный поиск по образцу.

const int Alphabet = 256;
const int Entries = 4; // количество вхождений, запомненное в таблице
const int CutOff = 100; // отсечка поиска по строке (чтобы не задерживаться на длинных образцах)
int offsets[Alpabet][Entries]; // offsets[c][] - индексы крайне правого, второго справа и т.д.

int lookup_offset(const char* pattern, int curpos, char ch)
{
  // смотрим в таблице
  for(int attempt=0; attempt<Entries; ++attempt)
  {
    int offs = offsets[ch][attempt];
    if(offs < curpos) return offs;
  }
  // смотрим в строке
  int cutoff = max(0, curpos-CutOff);
  while(curpos >= cutoff && pattern[curpos] != ch) --curpos;
  return curpos;
}

Следующее улучшение — это правило хорошего суффикса.
Строим таблицу повторного вхождения суффиксов данной длины (очевидно, не более N/2).
Например, для строки abbcdecdebcd эти значения будут 'd'=8,'cd'=7,'bcd'=2,'ebcd'=-1...
Таблицу можно построить за линейное время!

Теперь, встретив несовпадение 4-го символа (т.е. совпадение суффикса длиной 3), мы можем передвинуть образец так, чтобы текущая позиция в тексте совпала со вторым символом образца.

Оказывается, что и это ещё не всё! Пусть образец выглядит так: ....abcd....xbcd....xbcd
Для суффикса bcd, очевидно, предшествующее вхождение — в позиции 13. Но радости от него — никакой. Ведь если мы споткнулись на символе, не равном 'x', то продвинув до 13 позиции, заведомо споткнёмся на этом же месте.
Поэтому улучшенный вариант препроцессинга должен давать предшествующее вхождение окончательного суффикса. А то и список всех вхождений...

Здравствуйте, PK Sly, Вы писали:

PS>строки в текст.
PS>Как это сделать, креме как тупым поиском?

Для этого существует алгоритм Кнута-Морриса-Пратта, дающий скорость O(length(T)+length(P)),
а не O(length(T)*length(P)), как в случае с тупым поиском.

Идея состоит в следующем:

Пусть искомая строка P имеет длину n.
Для каждой позиции p
— рассмотрим подстроку P[0..p)
— найдём 0<=s<p-1 такое, что P[0..s) == P[s-p..p), т.е. голова подстроки совпадает с хвостом
— обозначим эту величину как функцию s(p)

Если s(p) — многозначна, то алгоритм требует брать максимальное значение (чтобы обеспечить минимальный сдвиг и случайно не пропустить ничего).

Теперь, если мы сканируем текст T, и выяснили, что начиная с позиции k, совпали p символов, T[k..k+p)==P[0..p), а T[k+p]!=P[p], то можно сразу передвинуть k+=p-s(p); p=s(p) и продолжить; если же p==0, то k++.
Осталось лишь по ходу дела запомнить наибольшее значение p и соответствующее ему положение k.

            k  s      p
T ----------xxxyyyyxxxc------------
P           xxxyyyyxxx----
P                  xxxyyyyxxx-----
                   k  p

Введём уточнение: s(p,c) = s(p) такое, что P[s]==c.
В этом случае s=s(p,T[k+p]), k+=p-s, p=s+1. (При p==0, как и ранее, k++).
Опять же, если функция многозначна, нужно брать наибольшие значения.
Теперь мы проверяем каждый символ из T не более 1 раза.

            k      s  p
T ----------xxxcyyyxxxc------------
P           xxxcyyyxxx----
                   xxxcyyyxxx----
                   k   p

Здравствуйте, Андрей Боровский, Вы писали:

АБ>Статья :
АБ>Алгоритмы поиска в тексте

Автор(ы): Андрей Боровский
Дата: 28.01.2002

АБ>Авторы :
АБ>Андрей Боровский

Вы хоть проверяли работоспособность поиска "по шаблону"?

Пробуем — вызываем WCMakeBMTable для шаблона 'a?c' и пытаемся найти вхождение в строку 'cdxkabclru'. И... не находим!

Здравствуйте, Андрей Боровский, Вы писали:

АБ>Статья :
АБ>Алгоритмы поиска в тексте

Автор(ы): Андрей Боровский
Дата: 28.01.2002

АБ>Авторы :
АБ>Андрей Боровский
во втором примере строку
while Pos < Length(S) do
надо заменить на
while Pos <= Length(S) do