Longest Common Substring

Q: 최장 공통 부분 문자열의 시간 복잡도는 얼마인가요?

동적 프로그래밍 솔루션은 O(n × m) 시간이 걸리고, 단일 행을 사용하면 O(m) 메모리가 필요합니다. 모든 시작점 쌍에서 확장하면 최악의 경우 O(n × m × min(n, m)) 입니다. 접미사 자동자는 훨씬 긴 프로그램을 작성해야 하는 대가로 약 O(n + m) 에 도달합니다.

Q: 가장 긴 공통 부분 문자열 자체를 어떻게 반환하나요?

어떤 셀의 값이 best 보다 클 때마다 해당 블록이 끝나는 s1 의 위치 i 도 기록하세요. 마지막에는 그 위치에서 끝나는 s1 의 부분 문자열이 best 개의 문자입니다. 엄격한 초과 비교를 사용하면 s1 에서 처음 발견한 가장 긴 블록이 유지됩니다.

보통동적 계획법

+10

두 문자열 s1과 s2가 주어집니다. 부분 문자열은 문자열에서 가져온 끊기지 않고 이어진 글자들의 나열로, 예를 들어 clockwork에서 ork가 있습니다. s1과 s2에 공통으로 포함된 가장 긴 부분 문자열을 찾아 그 길이를 반환하세요. 두 문자열에 공통으로 나타나는 글자가 없으면 답은 0입니다.

함수

longestCommonSubstring(s1: string, s2: string) → integer

s1string: 첫 번째 문자열
s2string: 두 번째 문자열
반환값integer: 두 문자열 모두에서 찾을 수 있는 가장 긴 문자 블록의 길이

제약 조건

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1과 s2는 영문 소문자로 이루어져 있습니다.

예제

입력: s1 = "clockwork"s2 = "workshop"
출력: 4
설명: work는 clockwork를 끝내고 workshop을 시작하므로 길이가 4인 공통 부분 문자열이며, 두 문자열에 모두 나타나는 더 긴 블록은 없습니다.

입력: s1 = "hammer"s2 = "harmed"
출력: 2
설명: ha와 me는 두 단어 모두에 있지만, 세 글자가 연속해서 나타나는 경우는 없습니다. 두 단어 모두 h, a, m, e가 그 순서대로 들어 있지만, harmed에는 a와 m 사이에 r이 있습니다.

후속 질문

롤링 해시를 사용해 주어진 길이 L의 공통 부분 문자열이 존재하는지 약 O(n + m) 시간에 검사한 다음, L에 대해 이진 탐색을 할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 시작 위치 쌍에서 일치하는 부분을 확장하면 같은 문자를 다시 읽게 됩니다. 대신 블록이 끝나는 위치를 살펴보세요. s1[i]와 s2[j]에서 끝나는 공통 블록은 두 위치의 바로 앞 문자에서 끝나는 블록보다 한 글자 더 길며, 두 문자가 다르면 비어 있습니다. 이러한 길이를 표로 만들면 O(n × m) 시간에 답을 구할 수 있습니다.

모든 시작 위치 쌍에서 확장하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

모든 공통 부분 문자열은 s1의 어떤 위치 i와 s2의 어떤 위치 j에서 시작합니다. 각 쌍에 대해 문자가 일치하는 동안 앞으로 이동하며 횟수를 셉니다. 가장 큰 횟수가 답입니다.

반복되는 텍스트에서는 이동 거리가 길어집니다. 두 문자열이 모두 a 1000개로 이루어져 있으면, 모든 쌍은 더 짧은 접미사의 끝까지 이동합니다. 문자 비교는 약 3.3 × 10^8회입니다. (i, j)에서의 이동은 한 문자 뒤인 (i+1, j+1)에서의 이동을 통째로 반복합니다.

알고리즘

best = 0으로 설정합니다.
s1의 모든 i와 s2의 모든 j에 대해 k = 0으로 설정합니다.
i+k와 j+k가 모두 각 문자열의 범위 안에 있고 s1[i+k] == s2[j+k]인 동안 k에 1을 더합니다.
가장 큰 k를 best에 저장하고 반환합니다.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

각 쌍에서 끝나는 블록 길이 표

핵심 아이디어

run[i][j]를 s1[i-1]과 s2[j-1]에서 정확히 끝나는 가장 긴 공통 연속 부분 문자열의 길이라고 하자. 0행과 0열의 값은 0이다. 이러한 부분 문자열에는 두 문자가 모두 포함되어야 한다. 두 문자가 다르면 공통 부분 문자열이 없으므로 셀의 값은 0이다. 두 문자가 같으면 이 쌍에 두 문자열에서 각각 한 글자 앞에서 끝나는 부분 문자열을 더한다. 즉, run[i-1][j-1] + 1이다. 모든 공통 부분 문자열은 어딘가에서 끝나므로, 답은 위치와 관계없이 가장 큰 셀의 값이다.

hammer와 harmed에서는 h끼리 만나 1이 되고, a끼리 만나 길이가 2로 늘어난 다음 r에서 연속이 끊긴다. hammer의 두 번째 m은 m과 r이 일치하지 않은 뒤 harmed의 m과 만나므로 길이 1에서 시작하고, e끼리 만나 길이가 2로 늘어난다. 어떤 셀도 3에 도달하지 않는다.

셀마다 한 번씩 비교한다. 두 문자열의 길이가 각각 1000자라면 텍스트가 무엇이든 비교 횟수는 약 100만 번이다.

알고리즘

n+1개의 행과 m+1개의 열로 이루어지고 모두 0인 run을 할당하고, best = 0으로 설정합니다.
i를 1..n 범위에서 반복하고, 그 안에서 j를 1..m 범위에서 반복하며 s1[i-1]와 s2[j-1]를 비교합니다.
일치하면 run[i][j] = run[i-1][j-1] + 1로 설정하고 best를 갱신합니다.
일치하지 않으면 해당 셀을 0으로 둡니다.
best를 반환합니다.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

오른쪽에서 왼쪽으로 업데이트되는 한 행

핵심 아이디어

각 셀은 왼쪽 위 대각선 방향에 있는 셀만 읽습니다. 따라서 j를 오른쪽에서 왼쪽으로 순회하면 m+1개의 숫자로 이루어진 배열 하나인 run에 표를 담을 수 있습니다. run[j]에 값을 쓸 때 run[j-1] 슬롯에는 이전 s1 문자의 값이 여전히 들어 있는데, 이것이 대각선 셀의 값입니다.

이제 불일치가 발생하면 해당 슬롯에 이전 행의 숫자가 들어 있으므로 명시적으로 0을 써야 합니다. 시간 복잡도는 O(n × m)으로 그대로이며, 메모리는 약 10^6개의 숫자에서 1001개로 줄어듭니다.

알고리즘

m+1개의 0으로 이루어진 배열 run을 만들고 best = 0으로 설정합니다.
s1의 각 문자 ch에 대해 j를 m부터 1까지 역순으로 확인합니다.
ch == s2[j-1]이면 run[j] = run[j-1] + 1로 설정하고 best를 갱신합니다.
그렇지 않으면 run[j] = 0으로 설정합니다.
best를 반환합니다.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

함정과 경계 사례

마지막 셀을 반환합니다. run[n][m]은 양쪽 문자열의 마지막 글자에서 끝나는 블록만 다룹니다. abc와 abd의 경우 값은 0이고, ab의 경우 값은 2입니다.
문자가 일치하지 않을 때 더 큰 이웃 값을 복사합니다. 이것이 부분 수열 규칙이며, 블록이 글자를 건너뛸 수 있게 합니다. hammer와 harmed의 경우 값은 2가 아니라 4입니다.
단일 행을 왼쪽에서 오른쪽으로 순회합니다. 대각선 값은 읽기 전에 덮어쓰이므로, a와 aa를 비교하면 값은 2가 됩니다.
단일 행에서 초기화를 건너뜁니다. s1의 이전 글자에서 가져온 길이가 남아 이후에 존재하지 않는 블록을 확장합니다.
경계 검사를 하지 않고 무차별 대입 방식을 순회합니다. zzzz와 zz를 비교하면 더 짧은 문자열의 끝을 넘어 읽습니다.

자주 묻는 질문3

최장 공통 부분 문자열과 최장 공통 부분 수열의 차이는 무엇인가요?

부분 문자열은 끊기지 않고 이어지는 문자들의 연속된 구간이고, 부분 수열은 순서를 유지하지만 중간에 간격이 있을 수 있습니다. hammer와 harmed의 최장 공통 부분 문자열의 길이는 2이고 최장 공통 부분 수열의 길이는 4입니다(hame). 표에서 불일치가 발생하면 부분 문자열 칸은 0으로 초기화되지만, 부분 수열 칸에는 이웃한 값 중 더 큰 값이 복사됩니다.

최장 공통 부분 문자열의 시간 복잡도는 얼마인가요?

동적 프로그래밍 솔루션은 O(n × m) 시간이 걸리고, 단일 행을 사용하면 O(m) 메모리가 필요합니다. 모든 시작점 쌍에서 확장하면 최악의 경우 O(n × m × min(n, m))입니다. 접미사 자동자는 훨씬 긴 프로그램을 작성해야 하는 대가로 약 O(n + m)에 도달합니다.

가장 긴 공통 부분 문자열 자체를 어떻게 반환하나요?

어떤 셀의 값이 best보다 클 때마다 해당 블록이 끝나는 s1의 위치 i도 기록하세요. 마지막에는 그 위치에서 끝나는 s1의 부분 문자열이 best개의 문자입니다. 엄격한 초과 비교를 사용하면 s1에서 처음 발견한 가장 긴 블록이 유지됩니다.

def longestCommonSubstring(s1, s2):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

s1 = "clockwork"
s2 = "workshop"

예상 출력

Longest Common Substring

함수

제약 조건

예제

힌트

풀이

모든 시작 위치 쌍에서 확장하기

각 쌍에서 끝나는 블록 길이 표

오른쪽에서 왼쪽으로 업데이트되는 한 행

함정과 경계 사례

자주 묻는 질문3

비슷한 문제