1

2 つの文字列と整数 'k' を取得し、長さ k の両方の文字列の共通部分文字列を返す関数を作成しようとしています。(複数ある場合はランダムに1つ返します)。LONGEST 共通部分文字列をチェックするオンラインのアルゴリズムはたくさんありますが、k の長さの部分文字列をチェックするアルゴリズムは見つかりませんでした。

ハッシュテーブルを最適化したい場合は、ハッシュテーブルが正しい方法だと思いますが、うまく取得できませんでした。

リストに 1 つ以上の長さのシーケンスがあるかどうかをチェックする関数しか書けませんでした。これが私が得たものです：

def repeat(st, k):
    for i in range(len(st) - k + 1):
        for j in range(i + 1, len(st) - k + 1):
            if st[i : i + k] == st[j : j + k]:
                return st[i : i + k]
    return False

これについて何か助けていただければ幸いです... :/

4

2 に答える 2

3

シンプルなバージョンはこれだけです：

def common_substr(a, b, k):
  for substr in (a[i:i+k] for i in range(len(a)-k+1)):
    if substr in b:
      return substr

特に非常に大きな入力文字列 (メガバイトのテキストなど) の場合、kこれは非効率的であり、長さの可能なすべての部分文字列のハッシュを構築するとk速度が向上する可能性があると思います。

def common_substr(a, b, k):
  substrs = set(a[i:i+k] for i in range(len(a)-k+1))
  for substr in (b[i:i+k] for i in range(len(b)-k+1)):
    if substr in substrs:
      return substr

しかし、これにはもっと賢いアルゴリズムがあると思います。比較的単純なstrstr()(文字列内の文字列を検索する) でも、誰もが実装できる単純な方法よりも効率的なソリューションがあります。

于 2013-05-08T19:20:29.510 に答える
1

これは決して効率的または巧妙な解決策ではありません。

def substrings_of(s, k):
    for i in xrange(0, len(s) - k):
        yield s[i:i+k]

def common_substr(a, b, k):
    for a_s in substrings_of(a, k):
        for b_s in substrings_of(b, k):
            if a_s == b_s:
                return a_s
于 2013-05-08T19:16:52.360 に答える