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