0

次の文字列を持つファイルがあるとしましょう

a a a b a a b a a b b a b

ファイルにアクセスすることはできませんが、一度に 1 文字を与える関数 FetchNextChar() にアクセスできます。

一致するパターンは a a b

総ヒット数はどうやって数えますか？

これが私が考えていることです。

  1. フェッチされた文字がパターン ('a') の最初の文字である場合は、それをキューに追加します
  2. pattern の次の文字と一致する場合、次の文字の連結リストの追加/作成を開始します

したがって、最初のフェッチの後、

Pattern -a 
Queue - a 

Then 

Pattern -a  a 
Queue[0] a->a 
Queue[1] a


3rd 
Pattern    a    a    b
Queue[0]   a -->a--> a    //doesn't match, dequeue
Queue[1]        a-> a
Queue[2]             a

これはうまくいくと思いますが、パターンの最初の文字と一致する文字が複数ある場合、キューに追加し続けてリストを増やし続けるという問題があります。

何かご意見は？

4

2 に答える 2

3

状態ベースのアルゴリズムを使用できます。

スリーステートアルゴリズム

'b'aが読み取られるたびに続行しstate=0、オンの場合はパターンの発生数が1つ増えることがわかりstate=2ます。a'a'が読み取られると、state=2明らかに次の状態になります。

ここでは、アルゴリズムを実装するPythonスクリプト 

stream = ['a','a','a','b','a','a','b','a','a','b','b','a','b']

state = 0 
nbMatch = 0

for c in stream:
    if c=='a':
        if state==0 or state==1:
            state = state+1
        #if state == 2: state=2
    else: #c=='b'
        if state==2:
            nbMatch = nbMatch+1
        state = 0
    print c, "   state=", state
print nbMatch
于 2013-03-01T08:58:42.757 に答える
2

これは、スライディング ウィンドウの a を計算するRabin-Karp アルゴリズムを使用して効率的に解決できますrolling hash。素朴なローリング ハッシュ関数は、文字の ASCII コードを合計することですが、この配列を使用primesして衝突を少なくすることができます。私はこれらをテストしました。素数であり、大きくて類似した文字列とパターンの一致でいくつかの衝突が発生しました:

primes[] = {13 , 7963 , 17443 , 27527 , 37879 , 48673 , 59407 , 70729 , 81883 , 93251 , 104789 , 116531 , 128239 , 139969 , 151783 , 163883 , 176159 , 188029 , 200257 , 212447 , 224831 , 237283 , 249517 , 262217 , 274661 , 287173};

上記のアルゴリズムが一致数を出力するための疑似コードは次のとおりです。

stream = "aaabaabaabbab";
pattern = "aab";
queue window;

patternHash = 0;
for ch in pattern:
    patternHash = patternHash + primes[ch - 'a']

first = readFromStream(stream)
window.enqueue(first)
windowHash = primes[first - 'a']
for i = 0 to pattern.size():
    ch = readFromStream(stream)
    window.enqueue(ch)
    windowHash = windowHash + primes[ch - 'a']

count = 0
for i = pattern.size() to stream.size():
    if windowHash == patternHash
        if window == pattern
            count = count + 1
    ch = readFromStream(stream)
    window.enqueue(ch)
    windowHash = windowHash - primes[window.first() - 'a']
    windowHash = windowHash + primes[ch - 'a']
    window.dequeue()

print count
于 2013-03-02T21:25:49.880 に答える