Детерминированные автоматы для поиска номера подпоследовательности в строке другой строки

Question

Детерминированные автоматы, чтобы найти количество подпоследовательностей в строке? Как я могу построить DFA, чтобы найти номер строки вхождения как подпоследовательность в другой строке?

например. В "ssstttrrriiinnngggg" у нас есть 3 подпоследовательности, которые образуют строку "string"?

Кроме того, обе строки, которые нужно найти и искать, содержат только символы из определенного набора символов. У меня есть идея хранить символы в стеке, выкладывая их соответственно, пока мы не совпадем, если не совпадем, нажмите снова. Пожалуйста, скажите решение DFA?

Answer 1

ПЕРЕКРЫТИЕ МАТЧЕЙ

Если вы хотите посчитать количество перекрывающихся последовательностей, вы просто создаете DFA, который соответствует строке, например

1 -(если см. S) -> 2 - (если см. T) -> 3 - (если см. R) -> 4 - (если см. I) -> 5 - (если см. N) -> 6 - (если см. г) -> 7

а затем вычислить количество способов нахождения в каждом состоянии после просмотра каждого символа с помощью динамического программирования. Смотрите ответы на этот вопрос для более подробной информации.

DP[a][b] = number of ways of being in state b after seeing the first a characters
         = DP[a-1][b] + DP[a-1][b-1] if character at position a is the one needed to take state b-1 to b
         = DP[a-1][b] otherwise

Начните с DP[0][b]=0 для b>1 и DP[0][1]=1.

Тогда общее количество перекрывающихся строк равно DP[len(string)][7]

НЕЗАКРЫВАЮЩИЕСЯ МАТЧИ

Если вы подсчитываете количество неперекрывающихся последовательностей, то, если мы предположим, что символы в сопоставляемом образце различны, мы можем использовать небольшую модификацию:

DP[a][b] = number of strings being in state b after seeing the first a characters
         = DP[a-1][b] + 1 if character at position a is the one needed to take state b-1 to b and  DP[a-1][b-1]>0
         = DP[a-1][b] - 1 if character at position a is the one needed to take state b to b+1 and DP[a-1][b]>0
         = DP[a-1][b] otherwise

Начните с DP[0][b]=0 для b>1 и DP [0] [1] = бесконечность.

Тогда общее количество неперекрывающихся строк равно DP[len(string)][7]

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