상향식 접근 방식으로 동적 프로그래밍을 사용하여 가장 긴 공통 부분 문자열을 찾아야 할 때 더 작은 문제에 대한 솔루션을 계산하는 방법을 정의할 수 있습니다. 이러한 작은 문제 결과는 반복해서 계산할 필요가 없습니다. 대신 필요할 때만 액세스할 수 있습니다. 이것은 당면한 더 큰 문제에 대한 솔루션을 개발하는 것으로 이어질 것입니다.
아래는 동일한 데모입니다 -
예시
def compute_lcw(string_1, string_2):
val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len]) 출력
The longest common substring is : bull
설명
- 두 개의 문자열을 매개변수로 사용하는 'compute_lcw'라는 메서드가 정의되어 있습니다.
- 두 문자열을 반복하고 두 문자열에서 일치하는 문자열이 있는지 확인합니다.
- 단일 문자가 발견되어도 다른 변수에 저장됩니다.
- 이 문자열이 끝날 때까지 계속되면 이 두 문자열에 다른 문자열이 공통적으로 사용됩니다.
- 두 개의 문자열이 정의되어 있고 이 두 개의 문자열을 전달하여 메소드를 호출합니다.
- 이 작업의 데이터는 변수에 할당됩니다.
- 그런 다음 콘솔에 출력으로 표시됩니다.