2

重複の可能性:
配列に n...n+m が含まれているかどうかを判断するアルゴリズム?

M > N で、2 つの配列があるとします。長さ M の 1 つが A と呼ばれ、長さ N の 1 つが B と呼ばれます。配列 B が配列 A に存在するかどうかを調べるより速い方法はありますか?

例えば：

A = [ 1 2 3 4 5 6 ]

B1 = [ 2 3 4 ]

したがって、配列 B1 は A に存在しますが、 [ 1 3 2 ] のようなものは存在しません。

これは基本的に、Java で char 配列を使用して isSubstring() のようなものを実装しています。

私が考えることができる唯一の方法は、O(n^2) で、A の各要素を B の最初の要素と比較し、一致を探すために B を反復処理することです。

この質問は面接でかなり一般的だと思うので、私の質問は、より速いアプローチがあるかどうかを尋ねています.

4

1 に答える 1

2

KMPが欲しい

アルゴリズムkmp_search：入力：文字の配列、S（検索対象のテキスト）文字の配列、W（検索された単語）出力：整数（Wが見つかるSのゼロベースの位置）

define variables:
    an integer, m ← 0 (the beginning of the current match in S)
    an integer, i ← 0 (the position of the current character in W)
    an array of integers, T (the table, computed elsewhere)

while m+i is less than the length of S, do:
    if W[i] = S[m + i],
        if i equals the (length of W)-1,
            return m
        let i ← i + 1
    otherwise,
        let m ← m + i - T[i],
        if T[i] is greater than -1,
            let i ← T[i]
        else
            let i ← 0

(if we reach here, we have searched all of S unsuccessfully)
return the length of S

複雑：

テーブルTが以前から存在していると仮定すると、クヌース-モリス-プラットアルゴリズムの検索部分の複雑さはO（k）です。ここで、kはSの長さ、Oはbig-O表記です。関数の開始と終了で発生する固定オーバーヘッドを除いて、すべての計算はwhileループで実行され、このループの反復回数の限界を計算します。これを行うために、最初にTの性質について重要な観察を行います。定義上、S [m +i]をW[i]と比較しているときに、S[m]で開始された一致が失敗した場合にTが失敗するように構成されます。次に、可能な一致はS [m +（i --T [i]）]で開始する必要があります。特に、次に可能な一致はmよりも高いインデックスで発生する必要があるため、T[i]<iとなります。この事実を使用して、ループが最大2k回実行できることを示します。各反復で、ループ内の2つのブランチのうちの1つを実行します。最初の分岐は常にiを増加させ、mを変更しないため、現在精査されているSの文字のインデックスm+iが増加します。2番目のブランチはmにi--T[i]を追加します。これまで見てきたように、これは常に正の数です。したがって、現在の潜在的な一致の開始位置mが増加します。ここで、m + i = kの場合、ループは終了します。したがって、ループの各分岐は、それぞれm + iまたはmのいずれかで増加し、m≤m+ iであるため、最大でk回到達できます。m= kの場合、確かにm +i≥kであるため、増加します。せいぜい単位の増分で、過去のある時点でm + i = kを持っていたに違いないので、どちらの方法でも実行されます。したがって、ループは最大2k回実行され、検索アルゴリズムの時間計算量がO（k）であることを示しています。

追加情報：

KMPアルゴリズムの効率

アルゴリズムの2つの部分は、それぞれO（k）とO（n）の複雑さを持っているため、アルゴリズム全体の複雑さはO（n + k）です。これらの複雑さは、WまたはSにいくつの反復パターンがあっても同じです。

于 2013-02-02T21:10:47.630 に答える