まず、p[i]パターン内の文字、パターンの長さ、mパターン$内の最後の文字、つまり を使用し$ = p[m-1]ます。
適切なサフィックス ヒューリスティック ケース 1 には 2 つの状況があります。
状況 1
次の例を考えてみましょう。
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
したがって、XXXパターン内の部分文字列cXXXbXXXcXXXcXXXは適切な接尾辞です。文字 で不一致が発生しますc。不一致の後、4 を右にシフトするか、8 にシフトする必要がありますか?
次のように 4 をシフトすると、同じ誤算が再び発生します ( bmismathes c)。
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again
したがって、この状況では、実際には 8 文字を右にシフトできます。
状況 2
別の例を見てみましょう
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
ここで4、8、またはそれ以上シフトできますか? 明らかに、8 つ以上シフトすると、パターンをテキストと一致させる機会を逃してしまいます。したがって、この状況では右に 4 文字しかシフトできません。
では、これら 2 つの状況の違いは何でしょうか。
違いは、最初のケースでは、一致しない文字cに適切な接尾辞 を加えたものXXXがcXXX、次の (右から数えて) 一致するXXXものとその前の文字を加えたものと同じであるということです。2 番目の状況でcXXXは、次の一致 (右から数えて) にその一致の前の文字を加えたものと同じではありません。
したがって、任意の GOOD SUFFIX ( と呼びましょう) について、これら 2 つの状況でのシフトを把握する必要があります。(1)パターン内の GOOD SUFFIX と GOOD SUFFIX の前のXXX文字 ( と呼びましょう) も一致します。c次の (右から数えて) 良いサフィックス + その前の文字の一致、(2) 文字と GOOD SUFFIX が一致しない
状況 (1) の場合、たとえばパターンがある0XXXcXXXcXXXcXXXcXXXcXXX場合、 の最初のテストが失敗した後、20 文字を右にシフトし、テストされたテキストにc揃えることができます。0XXX
これが20という数の計算方法です。
1 2
012345678901234567890123
0XXXcXXXcXXXcXXXcXXXcXXX
^ ^
不一致が発生する位置は 20 で、シフトされた部分文字列0XXXは 20 から 23 の位置になります。また0XXX、位置 0 から始まるため、20 - 0 = 20 となります。
状況 (2) の場合、この例のように0XXXaXXXbXXXcXXX、 の最初のテストがc失敗した後、右に 4 文字だけシフトして、bXXXテストされたテキストに揃えることができます。
これが数4の計算方法です。
0123456789012345
0XXXaXXXbXXXcXXX
不一致が発生する位置は 12 であり、その位置を占める次の部分文字列は位置8でbXXX始まり、12 - 8 = 4です。j = 12i = 8j - is[j] = j - i;
国境
すべての適切な接尾辞を検討するには、まずいわゆる とは何かを理解する必要がありborderます。境界線は、文字列のproper接頭辞とproper接尾辞の両方である部分文字列です。たとえば、文字列のXXXcXXX場合、Xは境界線でXXあり、境界線でもありXXXます。しかし、XXXcそうではありません。パターンのサフィックスの最も広い境界線の開始点を特定する必要があり、この情報は array に保存されf[i]ます。
どのように決定するのf[i]ですか？
を知っていると仮定し、f[i] = j他のすべてのf[k]si < k < mについては、位置 から始まる接尾辞の最も広い境界線が位置iで始まることを意味しjます。f[i-1]に基づいて検索したいf[i]。
たとえば、 patternaabbccaaccの場合、位置i=4の接尾辞はccaaccであり、その最も幅の広い境界線はcc( p[8]p[9]) であるため、j = f[i=4] = 8. f[i-1] = f[3]そして今、私たちが持っている情報に基づいて、、、f[4]...f[5]について知りたいのですf[3]が、接尾辞は今ですbccaacc。の位置でj-1=7、 はa!=p[4-1]ですb。だからbcc国境ではありません。
幅 >= 1 の境界線は、この例にあるように、 posin からbccaacc始まるb接尾辞の境界線で始まる必要があることがわかっています。の位置に最も広い境界線があります。そこで、 と比較して検索を続けます。そして、それらは再び等しくありません。現在、接尾辞はであり、位置 には長さゼロの境界線しかありません。だから今、それはです。したがって、 と比較して検索を続けます。それらは等しくなく、それが文字列の末尾です。次に、長さゼロの境界線のみがあり、10 になります。j = 8cccccj = f[8]9p[4-1]p[j-1]p[9] = c10j = f[9]10p[4-1]p[j-1]f[3]
プロセスをより一般的な意味で説明するには
したがって、f[i] = j次のような意味です。
Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
位置 の文字が@位置i - 1の文字と同じである場合、
、または. ボーダーはposition から始まるサフィックスです。?j - 1f[i - 1] = j - 1; --i; --j; f[i] = j;@x ... $j-1
しかし、 position の文字が position の文字と異なる場合は@、i - 1右側に検索を続ける必要があります。2 つの事実がわかっています: (1) 境界線の幅は、位置 から始まる幅よりも小さくなければならないことがわかりました。つまり、 よりも小さくなります。次に、境界線は文字で始まり、文字で終わる必要があります。そうしないと、空になる可能性があります。?j - 1jx...$@...$
これらの 2 つの事実に基づいて、部分文字列内x ... $(位置 j から m まで) で始まる境界線の検索を続けますx。次に、次の境界線は に等しくなければなりませjん 。次に、文字を の前の文字と比較します。それらが等しい場合、境界が見つかりました。そうでない場合は、j > m までプロセスを続けます。このプロセスは、次のコードで示されます。f[j];j = f[j];@xj-1
while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
ここで、条件p[i -1] != p[j-1] , this is what we talked about in situation (2), p[i] matchesp[j] , but p[i -1] !=を見て、 からにp[j-1]シフトします。つまり です。ijs[j] = j - i;
説明されていない唯一のことはif (s[j] == 0)、短い接尾辞が同じ境界線を持つ場合に発生するテストです。たとえば、パターンがあります
012345678
addbddcdd
と を計算するf[i - 1]とi = 4、 が設定されs[7]ます。ただし、 を計算するときf[i-1]、テストがない場合は再度i = 1設定します。これは、位置に不一致がある場合、右にシフトする (占有されている位置に揃える) のではなく(占有されている位置までシフトしない) ことを意味します。s[7]if (s[j] == 0)63bddcdd6addcdd
コードのコメント
void bmPreprocess1()
{
// initial condition, set f[m] = m+1;
int i=m, j=m+1;
f[i]=j;
// calculate f[i], s[j] from i = m to 0.
while (i>0)
{
// at this line, we know f[i], f[i+1], ... f[m].
while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
{
if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
}
// assign j-1 to f[i-1]
i--; j--;
f[i]=j;
}
}