Вот простой, но, возможно, не оптимальный алгоритм.Мы пытаемся сопоставить привязку в каждой последующей точке строки, запустив DFA, начиная с этой точки.Когда DFA запускается, мы записываем последнюю точку в строке, где DFA находился в состоянии принятия.Когда мы в конечном итоге достигнем конца строки или точки, в которой DFA больше не может продвигаться, мы можем вернуть совпадение, если мы прошли через принимающее состояние;другими словами, если мы сохранили принимающую позицию, которая будет концом матча.В противном случае мы возвращаемся к следующей начальной позиции и продолжаем.
( Примечание: в обоих алгоритмах псевдокода ниже, предполагается, что переменная, которая содержит строковый индекс, может иметь неопределенное значение.практическая реализация, это значение может быть, например, -1.)
В псевдокоде:
Set <start> to 0
Repeat A:
Initialise the DFA state the starting state.
Set <scan> to <start>
Set <accepted> to Undefined
Repeat B:
If there is a character at <scan> and
the DFA has a transition on that character:
Advance the DFA to the indicated next state
Increment <scan>
If the DFA is now in an accepting state, set <accepted> to <scan>
Continue Loop B
Otherwise, the DFA cannot advance:
If <accepted> is still Undefined:
Increment <start> and continue Loop A
Otherwise, <accepted> has a value:
Return a match from <scan> to <accepted> (semi-inclusive)
Проблема с вышеупомянутым алгоритмом состоит в том, что цикл B может выполнить произвольное числораз, прежде чем потерпеть неудачу и вернуться к следующей исходной позиции.Так что в худшем случае время поиска будет квадратичным по длине строки.Это может произойти, например, с шаблоном a*b и строкой, состоящей из большого числа a с.
Альтернативой является параллельное выполнение нескольких DFA.Каждый DFA соответствует отдельной отправной точке в шаблоне.Мы сканируем строку линейно;в каждой позиции мы можем создать новый DFA, соответствующий этой позиции, чье состояние является начальным.
Важно отметить, что не у каждой начальной точки есть DFA, поскольку нет необходимости хранить два DFA.с тем же состоянием.Поскольку поиск выполняется по первому совпадению в строке, если два DFA имеют одно и то же состояние, вероятным совпадением будет только то, которое имеет более раннюю начальную точку.Кроме того, как только какой-то DFA достигает принимающего состояния, больше нет необходимости сохранять какой-либо DFA, чья отправная точка наступает позже, что означает, что как только принимающее состояние достигается любым DFA, мы больше не добавляем новые DFA в сканирование.
Поскольку число активных DFA не превышает число состояний в DFA, этот алгоритм работает в O (NM), где N - длина строки, а M - количество состояний в DFA.На практике количество активных DFA обычно намного меньше, чем количество состояний (если только очень мало состояний).
Тем не менее, патологические наихудшие случаи все еще существуют, потому что преобразование NFA⇒DFA может экспоненциально увеличивать количествоштатов.Экспоненциального взрыва можно избежать, используя набор NFA вместо DFA.Удобно упростить переходы NFA с помощью NFA без ε, либо с помощью ε-замыкания на автомате Томпсона, либо с помощью построения автомата Глушкова.Использование автомата Глушкова гарантирует, что число состояний не превышает длину шаблона.
В псевдокоде:
Initialise a vector <v> of <index, state> pairs. Initially the vector
is empty, and its maximum size is the number of states. This vector is
always kept in increasing order by index.
Initialise another vector <active> of string indices, one for each state.
Initially all the elements in <active> are Undefined. This vector records
the most recent index at which some Automaton was in each state.
Initialise <match> to a pair of index positions, both undefined. This
will record the best match found so far.
For each position <scan> in the string:
If <match> has not yet been set:
Append {<scan>, <start_state>} to <v>.
If <v> is empty:
Return <match> if it has been set, or otherwise
return a failure indication.
Copy <v> to <v'> and empty <v>. (It's possible to recycle <v>,
but it's easier to write the pseudocode with a copy.)
For each pair {<i>, <q>} in <v'>:
If <i> is greater than the starting index in <match>:
Terminate this loop and continue with the outer loop.
If there is no transition from state <q> on the symbol at <scan>:
Continue with the next pair.
Otherwise, there is a transition to <q'> (if using NFAs, do this for each transition):
If the index in <active> corresponding to <q'> has already
been set to <scan>:
Continue with the next pair.
Otherwise, <q'> is not yet in <v>:
Append the pair {<i>, <q'>} at the end of <v>.
Set the the index in <active> at <q'> to <scan>.
If <q'> is an accepting state:
Set <match> to {<i>, <scan>}.