は、たとえば、文字列のリストを考えると「ランダム」の文字列のリスト上の少なくとも2つの要素

Question

最長プレフィックス存在を見つける：

myList = ["foo", "foobar", "football", "footbag", "bar"] 

は、リスト上の少なくとも2つの文字列の最長プレフィックス存在を見つけます：

Longest prefix is "footba" present in "football" and "footbag" 

リストは入力によって塗りつぶされ、すべてが共通の接頭辞を持つわけではありません。

オプションと考えるには、プレフィックスがリストの2つの文字列にあることで十分です。複数のオプションがある場合は、最長のオプションを返す必要があります。

私は、たとえば、すべての文字列の最長の共通のプレフィックスを取得する方法を見つけることができました私の研究で

：

一覧：["foo_a","foo_b","foo_c","fnord"]

出力：Longest common prefix is "f"

しかし、上の文字列私のリストは同じ文字で始まらないかもしれません。

Answer 1

この：あなたは、パフォーマンスを気にしない場合は最大を更新維持しながら

、あなたは単に、リスト内のすべての単語を反復処理し、残りの部分にそれら（その接頭辞）のそれぞれを比較することができます大雑把な実装であり、大規模なリストでは効率的ではありませんが、仕事が完了します。私はあなたが少し時間がある場合、言及されたプレフィックスを試してみることをお勧めしたいと思います、彼らはよりよく働くでしょう。

これは、フルサイズの単語から、2つの単語が同じプレフィックスを共有するまで、後方に機能します。単語の終わりを切り捨て、同じ単語が何回出現するかを数え、少なくとも2ならばそれを返します。

from collections import defaultdict 

def list_to_text(x): 
    x = list(map(str, x)) 
    first = '", "'.join(x[:-1]) #Join together (a, b, c) 
    if first: 
     return '" and "'.join((first, x[-1])) #Add the last element (a, b, c and d) 
    return x[0] #Return a single value if list length is 1 

def find_longest_prefix(x): 
    x_max = len(max(x, key=len)) 
    for i in range(1, x_max)[::-1]: 

     #Chop off the end of every word 
     trim = [j[:i] for j in x] 

     #Iterate through every unique value 
     result = defaultdict(list) 
     for j in set(trim): 
      result[trim.count(j)].append(j) 

     #Finish iterating if there are more than 2 words that share a prefix 
     highest_count = max(result) 
     if highest_count >= 2: 
      prefix = result[highest_count] 
      words = [j for k in prefix for j in x if j.startswith(k)] 
      return prefix, words 

myList = ["foo", "foobar", "football", "footbag", "bar"] 
prefix, words = find_longest_prefix(myList) 

#Put together the string 
print('The longest common prefix{} "{}" present in "{}".'.format(' is' if len(prefix) ==1 else 'es are', 
                   list_to_text(prefix), list_to_text(words))) 

結果の数に基づいて文字列を少しフォーマットします。あなたのリストはまだこのになります：

The longest common prefix is "footba" present in "football" and "footbag". 

しかし、このようなものになります結果の同じ長さと数を持つ別の接頭辞を追加：

The longest common prefixes are "footba" and "testin" present in "football", "footbag", "testing" and "testin". 

Answer 2

prefix trieのフォレストを構築し、2つの（ヌル以外の）子を持つ最も深いノードの「高さ」（ルートからどれくらい離れているか）を検索できます。このノードは、最も長い共通接頭辞を表します。

def common_prefix_size(s1, s2): 
    res, i = 0, 0 
    while i < min(len(s1), len(s2)): 
     if s1[i] == s2[i]: 
      res += 1 
      i += 1 
     else: 
      break 
    return res 



def longest_prefix(lst): 
    res = '' 
    maxsize = 0 
    for i in range(len(lst) - 1): 
     for j in range(i + 1, len(lst)): 
      t = common_prefix_size(lst[i], lst[j]) 
      maxsize = max(maxsize, t) 
      if maxsize == t: 
       res = lst[i][:maxsize] 
    return res 

myList = ["foo", "foobar", "football", "footbag", "bar"] 

print(longest_prefix(myList)) # footba