Find the First Occurrence in a String

Q: 문자열의 첫 번째 출현을 찾는 시간 복잡도는 얼마인가요?

모든 시작 위치를 확인하면 최악의 경우 O(n · m) 시간이 걸리며, 여기서 n 과 m 은 각각 haystack과 needle의 길이이고, 추가 공간은 O(1) 입니다. Knuth-Morris-Pratt 알고리즘은 문자가 무엇이든 O(n + m) 시간과 테이블에 O(m) 공간을 사용합니다.

Q: KMP 접두사 테이블은 어떻게 작동하나요?

needle의 각 접두사에 대해, 표에는 접미사이기도 한 가장 긴 진접두사의 길이가 저장됩니다. k 개의 문자가 일치한 뒤 불일치가 발생하면, 그 k 개의 문자는 needle의 접두사이며, lps[k-1] 는 그중 다음에 올 수 있는 일치 부분의 시작으로 사용할 수 있는 문자의 수를 알려 줍니다. aabaaab 의 표는 [0, 1, 0, 1, 2, 2, 3] 입니다.

쉬움배열과 문자열 투 포인터

+10

두 문자열 haystack과 needle이 주어집니다. 0부터 세어 needle이 처음 나타나는 haystack의 인덱스를 반환하세요. needle이 haystack에 나타나지 않으면 -1을 반환하세요. find나 indexOf와 같은 내장 부분 문자열 검색 함수를 호출하는 대신 직접 검색을 구현하세요.

함수

strStr(haystack: string, needle: string) → integer

haystackstring: 검색할 텍스트
needlestring: 찾을 문자열
반환값integer: needle의 첫 번째 복사본이 시작되는 인덱스이며, 없으면 -1

제약 조건

1 ≤ haystack.length ≤ 5 × 10⁴
1 ≤ needle.length ≤ 5 × 10⁴
두 문자열에는 소문자 영어 문자만 포함되어 있습니다.
needle은 haystack보다 길 수 있습니다. 그러면 나타날 수 없으므로 답은 -1입니다.

예제

입력: haystack = "bananarama"needle = "ana"
출력: 1
설명: 인덱스 1, 2, 3의 문자는 ana를 만듭니다. 두 번째 문자열은 인덱스 3에서 시작해 첫 번째 문자열과 겹치지만, 정답은 첫 번째 문자열이므로 1입니다.

입력: haystack = "pineapple"needle = "apples"
출력: -1
설명: apple는 인덱스 4에서 시작하고, 그 직후에 haystack이 끝나므로 needle의 마지막 s와 일치하는 문자가 없습니다. apples와 완전히 일치하는 부분이 없으므로 답은 -1입니다.

입력: haystack = "abcabcabd"needle = "abcabd"
출력: 3
설명: 인덱스 0에서의 시도는 abcab라는 다섯 글자와 일치한 다음, 찾는 문자열은 d를 원하지만 c를 만납니다. 일치하는 부분은 인덱스 3에서 시작해 마지막 d에서 끝납니다.

후속 질문

needle이 시작되는 모든 인덱스를 반환하되, 겹치는 항목도 포함하면서 여전히 O(n + m) 시간에 처리할 수 있나요?

힌트

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

3개 중 0개 열림

풀이

모든 시작 위치에서 needle을 비교하는 방법은 정확하지만, 거의 일치할 때는 느립니다. 끝부분에서 실패하는 긴 부분 일치는 버려지고, 다음 시작 위치에서는 거의 같은 문자를 다시 읽습니다. Knuth-Morris-Pratt 알고리즘은 이 작업을 재활용합니다. needle만으로 만든 테이블은 실패한 부분 일치 중 어느 정도를 계속 활용할 수 있는지 알려 주므로, 검색은 haystack에서 뒤로 이동하지 않으며 O(n + m) 시간에 끝납니다.

모든 시작 위치를 확인하세요

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

핵심 아이디어

haystack의 길이를 n, needle의 길이를 m이라고 하겠습니다. needle의 복사본은 0부터 n-m까지의 어떤 인덱스에서든 시작할 수 있습니다. 왼쪽에서 오른쪽으로 각 시작 위치를 확인하세요. 각 위치에서 needle과 haystack의 문자를 하나씩 비교하고, 처음 다른 문자가 나오면 멈춥니다. m개의 문자가 모두 일치하는 첫 시작 위치가 답이며, 왼쪽에서 오른쪽으로 확인하므로 첫 번째 복사본을 찾게 됩니다.

마지막 시작 위치가 n-m인 이유는 그보다 뒤에서 시작하는 복사본은 haystack의 끝을 넘어가기 때문입니다. 이 경계값은 needle이 haystack보다 긴 경우도 처리합니다. 시도할 시작 위치가 없으므로 루프가 끝까지 실행된 뒤 -1을 반환합니다.

대부분의 문자가 일치할 때 비용이 커집니다. a가 50,000개인 haystack과 a가 24,999개인 뒤에 b가 오는 needle을 생각해 보세요. 25,001개의 시작 위치마다 b에 도달하기 전에 25,000개의 문자를 비교하므로, -1이라는 답을 얻는 데 비교 횟수가 6 × 10^8회를 넘습니다.

알고리즘

n과 m을 각각 haystack과 needle의 길이라고 합시다.
0부터 n-m까지 각 start에 대해 j를 0으로 설정합니다.
j < m이고 haystack[start + j]가 needle[j]와 같으면 j를 증가시킵니다.
j가 m에 도달하면 모든 문자가 일치한 것입니다. start를 반환합니다.
어떤 시작 위치에서도 일치하지 않으면 -1을 반환합니다.

def strStr(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:
            return start
    return -1

Knuth-Morris-Pratt

핵심 아이디어

브루트 포스가 무엇을 버리는지 살펴보세요. abcabcabd에서 abcabd를 검색할 때, 인덱스 0에서 시작한 시도는 abcab까지 일치한 뒤 실패합니다. 이 다섯 글자는 ab로 끝나고, ab는 니들의 시작 부분이기도 합니다. 따라서 불일치가 발생한 뒤에도 다음 유효한 시도에서 두 글자는 이미 일치한 상태이므로, 헤이스택의 같은 위치에서 계속 검색할 수 있습니다.

문자열의 보더란 접두사이면서 접미사이기도 한 더 짧은 부분 문자열을 말합니다. 예를 들어 abcab에서 ab가 보더입니다. 검색하기 전에 lps 테이블을 만드세요. 여기서 lps[i]는 needle[0..i]의 가장 긴 보더의 길이입니다. abcabd의 경우 [0, 0, 0, 1, 2, 0]입니다. 이 테이블은 니들에만 영향을 받으며, 니들을 자기 자신과 비교하면서 동일한 매칭 루프를 실행해 만듭니다.

그런 다음 헤이스택을 한 번 훑으면서 지금까지 일치한 니들 글자 수인 k를 유지합니다. 다음 글자가 needle[k]와 같으면 k를 1 증가시킵니다. 다르면 k를 lps[k-1]로 설정하고, 일치하거나 k가 0이 될 때까지 같은 글자를 다시 비교합니다. 보더로 되돌아가도 일치하는 문자열을 건너뛰지는 않습니다. 실패한 시도 안에서 시작하는 모든 일치 문자열은 지금까지 일치한 부분의 보더로 시작해야 하며, 가장 긴 보더를 먼저 시도하기 때문입니다. k가 m에 도달하면 일치 문자열은 i-m+1에서 시작한 것입니다.

시간 복잡도가 선형인 이유는 다음과 같습니다. k는 헤이스택의 각 글자마다 최대 1씩 증가하고, 되돌아갈 때마다 감소합니다. 따라서 증가한 횟수보다 더 많이 감소할 수 없으므로, 전체 검색은 최대 2n단계가 걸리고 테이블을 만드는 데는 최대 2m단계가 걸립니다.

알고리즘

lps를 구성합니다. k = 0으로 설정하고, 1부터 m-1까지 각 i에 대해 k > 0이고 needle[i]가 needle[k]와 다를 동안 k = lps[k-1]로 되돌립니다. 두 값이 일치하면 k를 증가시키고, lps[i] = k를 저장합니다.
k를 0으로 초기화하고 인덱스 i로 haystack을 순회합니다.
k > 0이고 haystack[i]가 needle[k]와 다를 동안 k = lps[k-1]로 설정합니다.
haystack[i]가 needle[k]와 같으면 k를 증가시킵니다.
k가 m과 같으면 i-m+1을 반환합니다. 루프가 끝나면 -1을 반환합니다.

def strStr(haystack, needle):
    m = len(needle)
    # lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and needle[i] != needle[k]:
            k = lps[k - 1]
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k

    k = 0  # how many letters of needle are matched so far
    for i, ch in enumerate(haystack):
        while k > 0 and ch != needle[k]:
            k = lps[k - 1]  # fall back to the longest border, never move i back
        if ch == needle[k]:
            k += 1
        if k == m:
            return i - m + 1
    return -1

함정과 경계 사례

대부분의 버그는 haystack의 끝부분이나 폴백 루프 안에서 발생합니다.

시작 위치를 n-m 대신 n-1까지 이동시키는 경우입니다. haystack의 끝부분이 needle의 시작 부분과 일치하면, 비교 과정에서 haystack의 끝을 넘어 읽게 되어 Python, Java, Rust, Swift에서는 인덱스 오류가 발생합니다.
needle이 haystack보다 길 수 있다는 점을 잊는 경우입니다. C++의 size_t나 Rust의 usize처럼 부호 없는 길이에서는 n-m이 음수가 될 수 없습니다. C++에서는 큰 수로 래핑되고 Rust에서는 디버그 빌드에서 패닉이 발생합니다. 먼저 m > n을 확인하거나 부호 있는 정수로 계산하세요.
KMP 폴백을 while이 아니라 if로 작성하는 경우입니다. aabaa에서 aaa를 찾을 때, b에서는 2에서 1로, 다시 0으로 두 번 폴백해야 합니다. 한 번만 폴백하고 멈추면 b가 아무것과도 일치하지 않는데도 k가 1로 남아, 존재하지 않는 인덱스 2에서 일치한다고 보고하게 됩니다.
KMP에서 불일치가 발생한 뒤 haystack 인덱스를 뒤로 옮기는 경우입니다. 바뀌는 것은 k뿐입니다. i를 되돌리면 최악의 경우 시간 복잡도가 O(n · m)으로 돌아갑니다.
일치가 끝나는 위치나 1부터 세는 인덱스를 반환하는 경우입니다. 답은 0부터 세는 시작 위치입니다. Lua와 R의 문자열은 1부터 시작하므로 반환하기 전에 1을 빼세요.
PHP에서 최상위 수준에 strStr을 선언하는 경우입니다. PHP 함수 이름은 대소문자를 구분하지 않으므로 내장 함수 strstr과 충돌합니다. 그래서 PHP 시작 코드는 함수를 별도의 네임스페이스에 둡니다.

자주 묻는 질문3

문자열의 첫 번째 출현을 찾는 시간 복잡도는 얼마인가요?

모든 시작 위치를 확인하면 최악의 경우 O(n · m) 시간이 걸리며, 여기서 n과 m은 각각 haystack과 needle의 길이이고, 추가 공간은 O(1)입니다. Knuth-Morris-Pratt 알고리즘은 문자가 무엇이든 O(n + m) 시간과 테이블에 O(m) 공간을 사용합니다.

KMP 접두사 테이블은 어떻게 작동하나요?

needle의 각 접두사에 대해, 표에는 접미사이기도 한 가장 긴 진접두사의 길이가 저장됩니다. k개의 문자가 일치한 뒤 불일치가 발생하면, 그 k개의 문자는 needle의 접두사이며, lps[k-1]는 그중 다음에 올 수 있는 일치 부분의 시작으로 사용할 수 있는 문자의 수를 알려 줍니다. aabaaab의 표는 [0, 1, 0, 1, 2, 2, 3]입니다.

내장된 find 또는 indexOf를 사용하지 않는 이유는 무엇인가요?

프로덕션 코드에서는 그렇게 하는 것이 좋습니다. 테스트를 거쳤고 빠르기 때문입니다. 면접관은 올바른 경계를 사용해 일치하는 루프를 작성할 수 있는지 확인하려고 이 문제를 냅니다. 그리고 보통 이어지는 질문에서는 최악의 경우 O(n · m)이 되는 것을 어떻게 피할지 묻습니다. 내장 검색의 최악의 경우는 언어와 라이브러리 버전에 따라 달라지므로, 그 질문에 대한 답이 되지 않습니다.

def strStr(haystack, needle):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

haystack = "bananarama"
needle = "ana"

예상 출력