Python에서 두 개 이상의 문자열에서 가장 긴 공통 부분 문자열을 찾는 방법은 무엇입니까?

Longest Common Substring 알고리즘에 대한 공통 동적 프로그래밍 구현은 O(nm) 시간에 실행됩니다. 다음은 가장 긴 공통 부분 문자열 알고리즘의 구현입니다.

예시

def longest_common_substring(s1, s2):
   m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
   longest, x_longest = 0, 0
   for x in xrange(1, 1 + len(s1)):
       for y in xrange(1, 1 + len(s2)):
           if s1[x - 1] == s2[y - 1]:
               m[x][y] = m[x - 1][y - 1] + 1
               if m[x][y] > longest:
                   longest = m[x][y]
                   x_longest = x
           else:
               m[x][y] = 0
   return s1[x_longest - longest: x_longest]
print(longest_common_substring('wellbeing', 'welcome'))

출력

wel

이것이 작동하는 방식입니다.

• 처음에는 counter array(m)을 모두 0으로 초기화했습니다.

• 첫 번째 행부터 문자열 s1의 첫 번째 문자를 문자열 s2의 모든 문자와 비교합니다.

• s2의 문자를 탐색하는 동안 s1의 문자와 일치하면 카운터를 증가시킵니다. 대각선으로 한 단계 낮은 위치에 있는 m[i][j]로 저장됩니다.

마지막에 루프에서 계산한 인덱스를 사용하여 가장 긴 하위 문자열을 반환합니다.