1

2つの配列で見つかった要素の重複するインデックスを与えることができるアルゴリズムを構築したいと思います。

たとえば、文字列の配列が2つあります

Array1：{"a"、 "c"、 "h"、"d"、 "a"、 "o"、 "m" }

Array2：{ "d"、 "a"、 "o"、 "m"、 "c"、 "e"、 "o"、 "m"、 "c"、 "z"、 "e"、 "l" 、"p"、 "v"、 "c"、 "z"、 "c"}

このようにして、array1とarray2のインデックスが返されるはずです。

x1、y1 = {3,6} * x2、y2 = {0,3} *

これは、配列内の文字列のシーケンスが一致する必要があることを意味し、文字列値が一致する限り、それを実行し、すべてのレコードが以前のレコードの一致によって一意になるようにする必要があります。

回答と回答を待っています。質問がある場合はお知らせください。

例のように、データベースにレコードを挿入するテーブルがあり、挿入するすべてのレコードは非常に一意である必要があります。したがって、挿入時に、バッチで挿入する必要のあるレコードの配列があります。つまり、データベーステーブルのレコードは次の形式になっています。

colum1 hash1 hash2 hash3 hash4 hash5

そして、次の形式のレコードをデータベースに挿入したいと思います。hash3 hash4 hash5 hash6 hash7 hash8

次に、テーブルの結果は次のようになります。colum1 hash1 hash2 hash3 hash4 hash5 hash6 hash7 hash8

ただし、データベースに挿入する必要のある配列がhash2 hash3hash4hash6のような形式になる場合

次に、それはまったく新しいエントリとして扱われる必要があり、データベース全体に挿入されます。

今回は私の問題を詳しく説明することが明確になっていることを願っています

4

1 に答える 1

2

あなたが言及している問題は最長共通部分列問題と呼ばれます（文字列とLCSの頭字語に関する別の問題-最長共通部分列と混同しないでください）。いつものように、最良の説明はウィキペディアにあります：http: //en.wikipedia.org/wiki/Longest_common_substring_problem :)

つまり、文字列が本当に短く、非常に怠惰なプログラマーである場合、これを行う最も速い方法は、arr2のすべてのサブ文字列をarr1と照合することです。これには約n^2 * mの時間がかかります（長さがnの場合はarr2、長さがmの場合）-これは長い文字列の場合はかなりの時間です。

文字列が長い/怠惰でない場合は、接尾辞木を使用する最良のアルゴリズムを使用すると、実行時間が線形になります。

于 2012-05-01T14:52:00.950 に答える