가장 길게 반복되는 하위 문자열

Question

학교 공부를 위해 파이썬을 배웁니다. 기본적으로 here과 같이 문자열 목록에서 가장 긴 반복 부분 문자열을 찾아야합니다. 나는 this article을 통해 독서를하고 내가해야 할 일에 대해 이해하고 있습니다.

def long_rptr_subString(testList): 
    longSubstring = '' 

    if len(testList) > 1 and len(testList[0]) > 0: 
     for i in range(len(testList[0])): 
      for j in range(len(testList[0])-i+1): 
       if j > len(longSubstring) and all(testList[0][i:i+j] in x for x in testList): 
        longSubstring = testList[0][i:i+j] 
    return longSubstring 

을 지금은 이제 ['slide', 'glidb', 'flidt', 'cridz', 'bidr'] 나는 내 긴 문자열 인 것으로 'id'의 정확한 결과를 얻을 가정 해 봅시다 내 함수를 호출 할 때 다음과 같이

지금까지 내 구현입니다.

그러나 목록을 전달할 때 ['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah'] 결과가 반환되지 않습니다. 내가 내 가장 긴 부분 문자열로 'blah' 돌아올 수 있어야하지만, 나는 이것을 달성하는 방법을 찾지 못했습니다. 하위 문자열이 목록의 모든 항목에있을 때만 부분 문자열을 일치시킬 수있는 것 같습니다. 한 번 이상 발생하는 가장 긴 하위 문자열을 얻으려면 코드/논리를 어떻게 수정해야합니까?

감사합니다. 당신이 그 변화하더라도

all(testList[0][i:i+j] in x for x in testList) 

, 당신은 단지 처음 문자열에있는 가장 긴 문자열을 찾을 수 있기 때문에, : 그 정확히 당신이 무엇을 물어 때문에

Answer 1

만 all 항목에서 하위 문자열을 일치시킬 수 있습니다 testlist[0]을 통해서만 확인하십시오.

대신, 같은 시도 :

def longest_substr(lst): 
    longest = None 
    for word in lst: 
     for i in range(len(word)): 
      for j in range(i+1, len(word)+1): 
       if ((longest is None or (j - i > len(longest))) and 
        sum(word[i:j] in w for w in lst) > 1): 
        longest = word[i:j] 
    return longest 

이 단어 적어도 두 (> 1) (또는 빈 목록 또는 빈 문자열의 목록 것 return None)에있어 가장 긴 문자열을 발견하고 나를 준다 다음과 같은 결과 : 당신이 문자열은 모든 문자열에 있어야합니다 요구 사항을 제거하면,

>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr']) 
'lid' 
>>> longest_substr(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']) 
'blah' 

참고, 단어의 첫 번째 목록에서 가장 긴 실제로 'lid'입니다.

Answer 2

정말로 blah을 원하면 가장 긴 공통 부분 시퀀스가 ​​모든 문자열에 있어야한다는 조건을 제거해야합니다. 따라서 이것을 할 수 있습니다 (첫 번째 예는 lid입니다).

def allCommonSubstrings(s1, s2): 
    answer = set() 
    if len(s1) > len(s2): 
     s1, s2 = s2, s1 
    for i in range(len(s1)): 
     for j in range(i+1, len(s1)+1): 
      if s1[i:j] in s2: 
       answer.add(s1[i:j]) 
    return answer 

def longestCommonSubstring(strings): 
    common = set() 
    for s1,s2 in itertools.combinations(strings, 2): 
     common = common.union(allCommonSubstrings(s1, s2)) 
    return max(common, key=len) 

In [288]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr', 'balh', 'tejka', 'djakljskdl', 'blah', 'blah', 'blah']) 
Out[288]: 'blah' 

In [289]: longestCommonSubstring(['slide', 'glidb', 'flidt', 'cridz', 'bidr']) 
Out[289]: 'lid'