15

次の架空のインタビューの質問に対する答えが見つかりませんでした。

長さ N の 2 つの文字列シーケンスが与えられた場合、順序に関係なく、一致する部分文字列の最大長をどのように見つけることができますか。

たとえばseq1 = "ABCDEFG"、 およびが与えられた場合seq2 = "DBCAPFG"、最大長のウィンドウは 4 です ( ABCDfromseq1およびDBCAfrom seq2)。

4

3 に答える 3

8

これは O(n) ソリューションです (固定のアルファベット サイズと O(1) 辞書アクセスを想定しています)。

seq1 の文字をカウントアップし、seq2 の文字をカウントダウンする単一の度数分布表を使用します。このヒストグラムが再び同じ値を取る場合、一致するウィンドウが表示されます (これは、同じ数の中間文字が必要であることを意味するため)。

そのため、辞書を使用してヒストグラムの以前の値を保存します。

Python 実装:

def find_window(seq1,seq2):
    """Yield length of matching windows"""
    D={} # Dictionary with key=histogram, value = first position where this happens
    H=[0]*26 # H[x] is count of x in seq1 - count of x in seq2
    D[tuple(H)]=-1
    for i,(a,b) in enumerate(zip(seq1,seq2)):
        a=ord(a)-ord('A')
        b=ord(b)-ord('A') 
        H[a]+=1
        H[b]-=1
        key=tuple(H)
        if key in D:
            yield i-D[key]
        if key not in D:
            D[key]=i

print max(find_window("ABCDEFG","DBCAPFG"))

より大きなアルファベットがある場合は、完全なヒストグラムの代わりにハッシュ値のみを保存する同様の手法を使用できます。たとえば、単純に各文字のランダム コードを選択し、seq の各文字のコードを追加したり、seq2 の文字を減算したりできます。

ハッシュの競合が発生した場合に、提案された一致が正しいことを確認するために、2 番目のパスが必要になります。

于 2013-06-08T19:23:14.403 に答える
0

仮定

与えられた配列 A[0..n]、B[0..m] に対して

  • 有限アルファベット

  • 繰り返さない文字

     ans = -1
 j = index of A[0] in B
 if j > n then no substring exists
 for 1 .. n
     find A[i] in B[0..j]
     if not found
         j = find A[i] in B[j+1..m]
         if not found, return last ans
     else 
         if i == j then ans = j

B[0..j] がソートされた場合 (おそらく二分木 P を構築)、B[0..j] 内の A[i] の検索は O(log n) になり、アルゴリズム全体は O(n log n)

これを検証するのに役立ちます。
反例はありますか？

于 2013-06-08T19:19:20.220 に答える