7

KMPおよびZアルゴリズムは、文字列検索のよく知られたアルゴリズムです。

KMPアルゴリズムは、次のように定義されている KMP 失敗関数を介してパターンを見つけることを扱います (pat検索パターン)

lps[i] = pat[0..i] のサフィックスでもある pat[0..i] の最長の適切なプレフィックス。

たとえば、string "abcab"それは[0, 0, 0, 1, 2]

ここで、Zアルゴリズムは次のように定義される z 関数を使用します。

長さ n の文字列 S を指定すると、Z アルゴリズムは配列 Z を生成します。ここで、Z[i] は、pat のプレフィックスでもある pat[i] から始まる最長の部分文字列の長さです。

問題は、アルゴリズムZを使用して機能を実現できるかどうかです。KMP私が探しているのは、lps配列と同じ結果につながる配列のいくつかの変更Z[i]です。

4

3 に答える 3

3

注: アルゴリズムが間違っています

for i in range(0, len(s)):
    if lps[i] != 0:
        Z[i - lps[i] + 1] = lps[i]

その後、 inは位置で始まり、文字列のプレフィックスでもあるZ[i]サフィックスの最大長になります。i

編集

nikhil_vyas が指摘したように、提案されたアルゴリズムは問題を解決しません。それが実際に行うことはZ、配列を部分的に最長のサフィックスとその他のサフィックスで埋めることです。このような不完全な配列は、基本的に「文字列内で最も長いものを見つける」といういくつかの問題を解決するのに役立ちますが、質問には答えません。

私の頭に浮かぶZ配列を持つ配列を再構築する最も簡単な方法は、配列に対応する文字列を構築し、その文字列の配列を構築することです。しかし、それが「配列内のいくつかの変更」の定義に合っているかどうかはわかりません。lpslpsZlps

于 2013-09-17T14:36:43.190 に答える
0

Mikhail Melnik のソリューションは、"aaaaa" のような文字列のすべてのインデックスに対して Z を計算しない場合があります。最初の繰り返しで空のままになっているインデックスを埋めるために、追加の繰り返しが必要です。

for i in range(0, len(s)):
    Z[i - lps[i] + 1] = lps[i]
for i in range(0, len(s)):
    Z[i] = max(Z[i], Z[i - 1] - 1)                     `
于 2015-06-19T17:04:17.753 に答える