0

Boyer–Moore 文字列検索アルゴリズムを文字列に適用すると、次のようになります。

SSIMPLE EXAMPLE

パターンで：

EXAMPLE

アルゴリズムの流れは次のとおりです。

SSIMPLE EXAMPLE ---------------------(1)
EXAMPLE

SSIMPLE EXAMPLE ----------------------------(2)
      EXAMPLE

SSIMPLE EXAMPLE ----------------------------------(3)
        EXAMPLE

ただし、同じアルゴリズムを同じ文字列に適用する場合:

SSIMPLE EXAMPLE

ただし、パターンが少し異なります: (最初の E を T に置き換えます)

TXAMPLE

アルゴリズムの流れは次のとおりです。

SSIMPLE EXAMPLE ------------------- (1)
TXAMPLE

SSIMPLE EXAMPLE ----------------------(2)
       TXAMPLE

SSIMPLE EXAMPLE ---------------------------(3)
        TXAMPLE

最初の例から: 2 番目のステップでEは、下にあります。E

と 2 番目の例で: 2 番目のステップでTは、ではなくE、スペースの下

何故ですか ？TアルファベットとはそれぞれE単語TXAMPLEとにどのような違いをEXAMPLEもたらしますか?

4

1 に答える 1

0

例では、最初と最後の文字が同じであるため、最後の文字を一致させると、文字列のその位置に E があることがわかります。そのため、EXAMPLE をシフトしようとすると、その位置の E が example の最初の E と一致すると想定する必要があります。

TXAMPLE では、最後の文字は文字列の末尾にのみ出現するため、最後の文字に一致する場合は、次の試行された一致が最初の一致とまったく重複しないように文字列をシフトできます。 '文字列の末尾以外には一致しません。

于 2012-11-01T04:28:58.980 に答える