0

文字列内のサブシーケンスの数を見つけるための決定論的オートマトン? 別の文字列のサブシーケンスとして出現文字列の数を見つけるために DFA を構築するにはどうすればよいですか?

例えば。"ssstttrrriiinnngggg" には、文字列 "string" を形成する 3 つのサブシーケンスがあります。

また、検出される文字列と検索される文字列の両方に、特定の文字セットの文字のみが含まれています。一致するまで文字をスタックに格納し、一致しない場合は再度プッシュするという考えがあります。DFA ソリューションを教えてください。

4

1 に答える 1

0

重複一致

重複するシーケンスの数を数えたい場合は、文字列に一致する DFA を構築するだけです。

1 -(s を見た場合)-> 2 -(t を見た場合)-> 3 -(r を見た場合)-> 4 -(i を見た場合)-> 5 -(n を見た場合)-> 6 -(見た場合g)-> 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

b>1 および DP[0][1]=1 の場合、DP[0][b]=0 から開始します。

重複する文字列の総数は 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

b>1 および DP[0][1]=無限大の場合、DP[0][b]=0 から開始します。

次に、重複しない文字列の総数は DP[len(string)][7] です。

このアプローチでは、一致するパターンに繰り返し文字 (「文字列」など) が含まれている場合、必ずしも正しい答えが得られるとは限りません。

于 2014-01-26T18:20:47.237 に答える