목차
문제
- B 문자열이 A 문자열에 있는지 체크하고, 있다면 최초로 등장한 인덱스를 반환하는 문제입니다.
- 예시
-
Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0. -
Input: haystack = "leetcode", needle = "leeto" Output: -1 Explanation: "leeto" did not occur in "leetcode", so we return -1.
-
- 제약사항
- 1 <= haystack.length, needle.length <= 104
- haystack and needle consist of only lowercase English characters.
문제 풀이
풀이 1 : Sliding Window
- 풀이
- 단순하게 haystack에 있는 모든 문자열을 기준으로 시작해서 needle 단어가 있는지 체크하는 것입니다.
- 따라서 시간복잡도는 O(nm)이 됩니다.
- 코드
-
class Solution: def strStr(self, haystack: str, needle: str) -> int: n = len(haystack) m = len(needle) for i in range(n-m+1): flag = True for j in range(m): if haystack[i+j]!=needle[j]: flag = False break if flag: return i return -1
-
- 시간복잡도
- O(nm)
풀이 2 : Rabin-Karp(RK) Algorithm (Single Hash)
- 풀이
- Rabin-Karp Algorithm은 해당 문자열에 대한 해시값을 구하고, 해시값을 비교해서 같은 문자인지 체크하는 알고리즘입니다.
- 파이썬에서 해시값은 ord를 통해 구해줄 수 있습니다. (아니면 임의로 지정해서 사용하는 방법도 가능합니다.)
- 각문자 별로 해시값을 적용하고 최대한 문자열에 대한 해시값이 겹치는 것을 줄여주기 위해 문자열 위치별로 위치 가중치를 곱해줍니다. 알파벳을 예시로 들면 아래와 같이 적용할 수 있습니다. (알파벳은 총 26개)
- a를 0 b를 1 c를 2 등으로 매핑한다고 하면 aac의 경우 0*(26^(2)) + 0*(26^(1)) + 2*(26^(0)) 이 됩니다. (십진수를 표현할 때 142의 경우 1*10^(2)+4*10^(1)+2*10^(0)이 되는 것과 똑같은 원리입니다.)
- 해시값을 계산하다 보면 그 해시값 자체가 엄청나게 커질 수 있는데 이를 방지하기 위해 큰 소수(예를 들면 10**9+33)로 나눠줍니다.
- 이로 인해 해쉬값 충돌이 발생합니다.
- 나머지 연산을 할 땐 나머지 법칙을 이용해 계산과정 중 커진 값들을 작아지게 만들어줍니다
- (A*B)%C = ((A%C)*(B%C))%C
- (A+B)%C = ((A%C)+(B%C))%C
- 해시값이 겹칠 수 있는데 이럴 경우 문자열이 같은지 실제로 체크를 진행해주어야 합니다.
- 즉, 최악의 경우 시간복잡도가 O(nm)이 될 수 있습니다.
- A문자열을 기준으로 각 문자열마다 B문자열 길이만큼의 해쉬값을 계산해주게 되면 결국엔 O(nm)이 걸리게 됩니다. 이를 방지하기 위해 rolling hash 방식을 통해 첫글자에 대해 m글자만큼의 해쉬값을 구하고, 그 뒤에 제일 앞글자의 해쉬값을 빼줌과 동시에 바로 뒷글자의 해쉬값을 더해주게 되면 그 다음 글자에 대한 m글자만큼의 해쉬값이 구해질 것입니다.
- 예를 들어 bcdef 가 있을때 3글자에 대한 해쉬값을 구한다고 하면 기존에는 bcd, cde, def 모두 각각 해쉬값 계산을 진행해야했습니다. (bcd : 1*(26^(2)) + 2*(26^(1)) + 3*(26^(0)) / cde : 2*(26^(2)) + 3*(26^(1)) + 4*(26^(0)) / def : 3*(26^(2)) + 4*(26^(1)) + 5*(26^(0)) )
- 하지만 rolling hash를 사용하면 처음 bcd 값에서 가장 앞의 1*(26^(2))를 제외하고 나머지 값에 26을 곱하고 바로 뒷글자인 e에 대한 해쉬값을 더해주면 됩니다.
- ( 1*(26^(2)) + 2*(26^(1)) + 3*(26^(0)) - 1*(26^(2))) * 26 + 4*(26^(0)) [e에 대한 해쉬값]
- Rabin-Karp Algorithm은 해당 문자열에 대한 해시값을 구하고, 해시값을 비교해서 같은 문자인지 체크하는 알고리즘입니다.
- 코드
-
class Solution: def strStr(self, haystack: str, needle: str) -> int: n = len(haystack) m = len(needle) if n < m: return -1 alpha_hash = {item:i for i,item in enumerate(list("abcdefghijklmnopqrstuvwxyz"))} RADIX = len(alpha_hash) MOD = int(1e9)+33 needle_hash = 0 haystack_hash = 0 weight = 1 for i in reversed(range(m)): needle_hash+=(alpha_hash[needle[i]]*weight)%MOD haystack_hash+=(alpha_hash[haystack[i]]*weight)%MOD if i==0: break weight = (weight*RADIX) % MOD needle_hash %= MOD haystack_hash %= MOD if needle_hash == haystack_hash: # 가장 처음 해쉬가 같은경우 문자열 체크 if needle==haystack[:m]: return 0 for i in range(1,n-m+1): haystack_hash = (haystack_hash-(alpha_hash[haystack[i-1]]*weight)%MOD + MOD)%MOD haystack_hash = ((haystack_hash*RADIX)%MOD+alpha_hash[haystack[i+m-1]])%MOD if needle_hash == haystack_hash: # 가장 처음 해쉬가 같은경우 문자열 체크 if needle==haystack[i:i+m]: return i return -1
-
- 시간복잡도
- 기본적으로 O(n+m)이지만, 최악의 경우 O(nm)이 될 수 있습니다.
- 문자열 haystack 해시진행(n), 문자열 needle 해시진행(m) → O(n+m)
- 해시 충돌이 발생하면 해당 문자열을 실제로 비교작업을 해주어야합니다. → O(nm)
- 기본적으로 O(n+m)이지만, 최악의 경우 O(nm)이 될 수 있습니다.
풀이 3 : Rabin-Karp(RK) Algorithm (Double Hash)
- 풀이
- Double Hash의 경우 Single Hash에 비해 충돌확률을 극도로 낮춰 거의 충돌이 없어 시간복잡도가 O(n)으로 간주됩니다.
- 두 개의 hash값을 계산해 놓고 비교합니다. 두 개의 hash 값이 모두 같은 경우는 거의 없으므로 문자열끼리 비교하는 경우가 거의 존재하지 않습니다.
- RADIX2와 MOD2를 다르게 설정해 처음 hash값이 겹치더라도 두 번째 hash값이 겹치지 않도록 설정해 줍니다.
- Double Hash의 경우 Single Hash에 비해 충돌확률을 극도로 낮춰 거의 충돌이 없어 시간복잡도가 O(n)으로 간주됩니다.
- 코드
-
class Solution: def strStr(self, haystack: str, needle: str) -> int: n = len(haystack) m = len(needle) if n < m: return -1 alpha_hash = {item:i for i,item in enumerate(list("abcdefghijklmnopqrstuvwxyz"))} RADIX = len(alpha_hash) MOD = int(1e9)+33 RADIX_2 = 31 # RADIX_1보다 큰 임의의 소수 MOD_2 = int(1e9)+37 needle_hash = 0 haystack_hash = 0 weight = 1 needle_hash_2 = 0 haystack_hash_2 = 0 weight_2 = 1 for i in reversed(range(m)): needle_hash+=(alpha_hash[needle[i]]*weight)%MOD haystack_hash+=(alpha_hash[haystack[i]]*weight)%MOD needle_hash_2+=(alpha_hash[needle[i]]*weight_2)%MOD_2 haystack_hash_2+=(alpha_hash[haystack[i]]*weight_2)%MOD_2 if i==0: break weight = (weight*RADIX) % MOD weight_2 = (weight_2*RADIX_2) % MOD_2 needle_hash %= MOD haystack_hash %= MOD needle_hash_2 %= MOD_2 haystack_hash_2 %= MOD_2 if (needle_hash == haystack_hash) and (needle_hash_2 == haystack_hash_2): # 가장 처음 해쉬가 같은경우 문자열 체크 return 0 for i in range(1,n-m+1): haystack_hash = (haystack_hash-(alpha_hash[haystack[i-1]]*weight)%MOD + MOD)%MOD haystack_hash = ((haystack_hash*RADIX)%MOD+alpha_hash[haystack[i+m-1]])%MOD haystack_hash_2 = (haystack_hash_2-(alpha_hash[haystack[i-1]]*weight_2)%MOD_2 + MOD_2)%MOD_2 haystack_hash_2 = ((haystack_hash_2*RADIX_2)%MOD_2+alpha_hash[haystack[i+m-1]])%MOD_2 if (needle_hash == haystack_hash) and (needle_hash_2 == haystack_hash_2): return i return -1
-
- 시간복잡도
- O(n)
풀이 4 : Knuth-Morris-Pratt (KMP) Algorithm
- 풀이
- KMP 알고리즘은 단어를 Sliding Window 방식으로 전체 단어의 모든 글자 기준을 시작점으로 타겟 단어가 있는지 체크하는 방식이 아닌, 전체 단어의 모든 글자를 타겟단어와 비교해나가면서, 만약 타겟단어와 틀린글자가 있다면, 그냥 다음 단어부터 다시 타겟단어와 비교하며 찾아나가는 과정입니다.
- 예를 들어, trailtrain이라는 문자열 속에서 train이라는 단어를 찾아야 하는 상황이라고 할 때, 기존 Sliding Window 방식은 0번 인덱스 기준(t) train 찾고 , 만약 틀리면 다시 1번 인덱스 기준(r) train인지 체크를 진행해 나갑니다.
- 이와 달리 KMP 알고리즘은 trailtrain이라면 l에서 n과 달라서 틀리기 때문에 r로 돌아가서 다시 검사하는 것이 아닌 l 다음 단어인 t부터 체크를 진행하는 것입니다.
- 하지만 위와 같은 방식으로만 진행하면 아래와 같은 경우는 정확히 타겟단어가 있는지 체크를 진행할 수 없습니다. 따라서 타겟 단어와 다른 글자가 있는 위치에서 그 앞부분이 타겟단어의 시작 부분과 겹치는 글자들이 있는지 체크를 추가로 진행해주어야 합니다. (즉, LPS를 통해 해당 글자에서 접두사와 접미사가 같은 것의 개수를 기록해 둡니다.)
- 위 예시에서 memem 부분에서 틀렸는데 마지막 m글자 기준 앞부분 단어인 meme에서 e 기준 접두사와 접미사가 같은 부분이 me이기 때문에 앞에 memes 중에서 앞에 me가 체크되었다고 생각하고 mes만 체크해 주면 됩니다. (즉, 현재 틀린 글자 m 기준 거기서부터 mes를 다시 체크해주면 됩니다.)
- 접두사와 접미사가 같은 부분의 글자수 개수
- (m기준) m : 0
- (e기준 ) me : 0
- (m기준) mem : 1 [m]
- (e기준) meme : 2 [me]
- (s기준) memes : 0
- 즉, KMP 알고리즘은 접두사와 접미사가 같은 개수를 체크해 두어 효율적으로 검색 단어를 찾는 방법입니다.
- LPS 구현
-
longest_border = [0] * m prev = 0 i = 1 while i < m: if needle[i] == needle[prev]: prev += 1 longest_border[i] = prev i += 1 else: if prev == 0: longest_border[i] = 0 i += 1 else: prev = longest_border[prev - 1]
- (prev는 비교하는 대상의 글자수입니다. 따라서 접두사 마지막 글자에 해당하는 인덱스는 prev-1이 됩니다. 접두사 다음 글자의 인덱스는 prev가 될 것입니다. (인덱스는 0부터 시작하므로))
- prev = longest_border[prev - 1] 로 가는 이유는 현재 글자가 다르다고 다시 맨 앞부터 비교하지 않게 하기 위함입니다.
- 만약 타겟단어 abceabcf 와 전체단어 abceabceabcf 가 있을 때 abceabc까지는 같은데 e랑 f가 다른 경우가 있다고 해봅시다. 그러면 e 앞글자인 abceabc를 다시 비교할 필요 없이 abceabc의 접두사 접미사 대칭 부분인 abc의 바로 뒷글자인 e(타겟)와 다시 e(전체)를 비교를 진행하면 됩니다. 이렇게 하면 처음부터 체크할 필요 없이 지금까지 체크한 글자를 기준으로 접두사와 접미사가 같은 부분의 접두사는 생략하고 그 접두사 뒷부분부터 체크를 진행하면 됩니다.
- (즉, 현재 글자가 다르다고 맨 앞글자부터 다시 비교할 필요 없이 계속 접두사의 접두사의 접두사를 체크해 보면 체크하는 글자수가 줄어듭니다.)
- (abaCabaFabaCaba까지 같은 글자인 것을 체크했다면 만약 그다음 글자가 다르더라도 접미사와 접두사가 같은 글자가 있기 때문에 이경우에는 뒷부분 abaCaba(접미사) 체크했던 것을 앞부분 abaCaba(접두사)을 체크했다고 생각하고 앞부분 다음 글자인 F부터 다시 체크를 진행해나가면 됩니다. 여기서 만약 또 다음글자 F랑 현재 글자가 다르다고 한다면 다시 뒷부분aba(접미사) 체크했던것을 앞부분 aba(접두사)을 체크했다고 생각하고 앞부분 다음 글자인 C와 다시 체크를 진행하면 됩니다. 여기서 만약 C와 현재 글자가 같다면 abaC부터 다시 타겟단어와 일치하는 단어들을 찾아나가게 되는 것입니다.
- 정리하면 현재까지 체크한 글자들이 타겟글자들과 같은데 만약 haystack의 다음 글자에서 타겟글자와 다르다고 한다면 현재까지 체크한 타겟글자들의 접두사의 다음 글자랑 haystack의 다음 글자와 비교하면 됩니다.(이렇게 하면 접미사체크했던 것을 접두사 체크했던 것으로 생각해서 시간을 단축할 수 있습니다.)
- 예시 1 [ababcababcabab]
- (i=1, prev=0) hay[1]=b, hay[0] =a 다르고, prev가 0이므로 더 이상 접두사로 이동불가. 따라서 LPS[1]=0 / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트)
- (i=2, prev=0) hay[2]=a, hay[0] =a 같으므로, prev +=1 / LPS[2]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트)
- (i=3, prev=1) hay[3]=b, hay[1] =b 같으므로, prev +=1 / LPS[3]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트)
- (i=4, prev=2) hay[4]=c, hay[2] =a 다르므로, 현재 prev 글자의 앞부분 글자의 접두사글자로 이동(앞뒤가 대칭이므로) prev = IPS[prev-1] (prev는 항상 체크하고자하는 글자 인덱스입니다. 따라서 앞글자까지의 인덱스는 prev-1이 될것입니다.) (즉, aba랑 abc에서 a랑 c가 같은지 비교했는데 다르므로 그 앞 타겟단어인 ab의 IPS로 이동합니다. 대칭 글자가 있는지 체크, prev = IPS[1] = 0)
- (i=4, prev=0) hay[4]=c, hay[0]=a 다르고, prev가 0이므로 더 이상 접두사로 이동불가. 따라서 LPS[4]=0 / i+=1
- (i=5, prev=0) hay[5]=a, hay[0] =a 같으므로, prev +=1 / LPS[5]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트)
- (i=6, prev=1) hay[6]=b, hay[1] =b 같으므로, prev +=1 / LPS[6]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트)
- 이런 식으로 쭈욱 진행
- 예시 2 [ abaCabaF ]
- (i=1, prev=0) hay[1]=b, hay[0] =a 다르고, prev가 0이므로 더 이상 체크할 단어가 없습니다. 따라서 LPS[1]=0 / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (LPS는 현재까지의 단어에 대해 접두사와 접미사가 같은 글자 개수입니다.)
- (i=2, prev=0) hay[2]=a, hay[0] =a 같으므로, prev +=1 / LPS[2]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (a가 같음)
- (i=3, prev=1) hay[3]=C, hay[1] =b 다르므로, LPS[prev-1] (즉, 체크를 진행하던 앞단어까지의 접두사 다음 글자)에 대하여 다시 체크를 진행합니다.( prev = IPS[1-1] = IPS[0] = 0 )
- (i=3, prev=0) hay[3]=C, hay[0] =a 다르고, prev가 0이므로 더 이상 체크할 단어가 없습니다. 따라서 LPS[3]=0 / i+1
- (i=4, prev=0) hay[4]=a, hay[0] =a 같으므로, prev +=1 / LPS[4]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (a가 같음)
- (i=5, prev=1) hay[5]=b, hay[1] =b 같으므로, prev +=1 / LPS[5]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (ab가 같음)
- (i=6, prev=2) hay[6]=a, hay[2] =a 같으므로, prev +=1 / LPS[6]=prev / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (abc가 같음)
- (i=7, prev=3) hay[7]=F, hay[3] =C 다르므로, LPS[prev-1] (즉, 체크를 진행하던 앞단어까지의 접두사 다음 글자, abaC에서 aba의 LPS인 1로 이동 (즉, a다음 글자인 b를 체크하기 위함))에 대하여 다시 체크를 진행합니다.( prev = IPS[3-1] = IPS[2] = 1 )
- 만약 aba가 아니라 aFa였다면, aFa의 LPS인 1로 이동하면 aF로 바로 IPS[7]=2가 될 것입니다.
- 이런 식으로 지금까지 체크했던 타겟단어와 같은 앞부분에 대해서 접미사와 같은 접두사가 있다면 해당 접두사 단어로 이동해서 그 타겟단어의 접두사 다음 글자부터 다시 체크를 진행해 주면 시간절약을 할 수 있습니다.
- (i=7, prev=1) hay[7]=F, hay[1] =b 다르므로, LPS[prev-1] (즉, 체크를 진행하던 앞단어까지의 접두사 다음 글자, ab에서 a의 LPS인 0로 이동 (즉, 0이면 타겟글자 제일 앞글자 a와 비교))에 대하여 다시 체크를 진행합니다.( prev = IPS[1-1] = IPS[0] = 0 )
- (i=7, prev=0) hay[7]=F, hay[0] =a 다르고, prev가 0이므로 더 이상 체크할 단어가 없습니다. 따라서 LPS[1]=0 / i+=1 (LPS가 업데이트되면 항상 i도 같이 업데이트) (LPS는 현재까지의 단어에 대해 접두사와 접미사가 같은 글자 개수입니다.)
- 탐색 코드 구현
- 탐색 코드 부분도 LPS를 생성하는 것과 코드가 비슷합니다. 차이점은 아래와 같습니다.
- LPS 생성 코드는 target 단어 기준 i=1, prev=0부터 시작이지만, 탐색 코드 부분은 전체 단어 기준 i=0, prev=0이 됩니다. 명칭 또한 prev가 아닌 needle_pointer가 됩니다.
- LPS를 생성할 때는 타겟단어와 타겟단어앞부분과 비교를 진행 (접두사와 접미사 같은 개수를 찾기 위함) (따라서 i=1, prev=0부터 시작)
- 탐색 코드 부분은 전체단어와 타겟단어를 비교를 진행 (LPS처럼 전체 단어를 체크하다가 prev 값이 타겟단어와 길이가 같아지면 해당 부분까지의 단어가 타겟단어와 일치하는 부분입니다.) (따라서 i=0, needle_pointer=0부터 시작)
- LPS 코드에서 LPS 리스트 값 업데이트 부분을 삭제하면 됩니다.
- 추가로 needle_pointer가 m이 되면 haystack_pointer-needle_pointer값을 return 하면 해당 단어 시작 부분이 return 됩니다. (타겟글자들을 다 찾은 것입니다.)
- LPS 생성 코드는 target 단어 기준 i=1, prev=0부터 시작이지만, 탐색 코드 부분은 전체 단어 기준 i=0, prev=0이 됩니다. 명칭 또한 prev가 아닌 needle_pointer가 됩니다.
- onioni 에서 i랑 s가 달라 특정단어 체크가 틀리게 되었습니다.
- 이경우 onion 단어의 마지막 n부분의 LPS를 보면 2입니다. (on가 접두사와 접미사) 따라서 타겟단어 onions 중에서 ions만 체크를 진행해 주면 됩니다.
- needlePointer를 LPS[needlePointer-1]부분으로 옮겨줍니다. s부분에서 i로 옮기는 것
- haystackPointer는 계속해서 체크를 진행해 나아가면 됩니다.
- 탐색 코드 부분도 LPS를 생성하는 것과 코드가 비슷합니다. 차이점은 아래와 같습니다.
- KMP 알고리즘은 단어를 Sliding Window 방식으로 전체 단어의 모든 글자 기준을 시작점으로 타겟 단어가 있는지 체크하는 방식이 아닌, 전체 단어의 모든 글자를 타겟단어와 비교해나가면서, 만약 타겟단어와 틀린글자가 있다면, 그냥 다음 단어부터 다시 타겟단어와 비교하며 찾아나가는 과정입니다.
- 코드
-
class Solution: def strStr(self, haystack: str, needle: str) -> int: n = len(haystack) m = len(needle) LPS = [0 for _ in range(m)] i = 1 prev = 0 while i<m: if needle[i]==needle[prev]: # 현재 글자 일치 (prev 위치 글자 = 현재 글자) prev+=1 # 개수를 의미하므로 1을 증가 LPS[i]=prev i+=1 # LPS 업데이트하면 다음 글자 체크 진행 else: # 다를 경우 if prev==0: # 0번째 글자와도 다르면 더이상 체크할 글자가 없음 LPS[i]=0 i+=1 else: # prev글자 이전까지의 단어의 접두사=접미사 인 접두사 다음 글자 위치로 이동 # LPS는 접두사=접미사 글자 개수를 의미하므로 인덱스로 생각하면 접두사 다음 글자를 의미 prev = LPS[prev-1] i=0 needle_pointer = 0 while i<n: if haystack[i]==needle[needle_pointer]: # 타겟단어 needle_pointer 글자와 현재 글자 일치 needle_pointer+=1 i+=1 if needle_pointer == m: return i-needle_pointer else: if needle_pointer == 0: # 제일앞 글자도 다르면 그냥 다음으로 진행 i+=1 else: # needle_pointer글자 이전까지의 단어의 접두사=접미사 인 접두사 다음 글자 위치로 이동 needle_pointer = LPS[needle_pointer-1] return -1
-
- 시간복잡도
- O(n)
- 비슷한 문제 : [백준 1786] 찾기
- 코드
-
import sys input = sys.stdin.readline t = input() p = input().rstrip() i = 1 prev = 0 lps = [0 for _ in range(len(p))] while i < len(p): if p[i] == p[prev]: prev += 1 lps[i] = prev i += 1 else: if prev == 0: lps[0] = 0 i += 1 else: prev = lps[prev - 1] i = 0 p_point = 0 answer = [] while i < len(t): if t[i] == p[p_point]: p_point += 1 i += 1 if p_point == len(p): answer.append(i - p_point + 1) p_point = lps[p_point - 1] else: if p_point == 0: i += 1 else: p_point = lps[p_point - 1] print(len(answer)) print(" ".join(map(str, answer)))
-
- 코드
알게 된 내용
- Rabin-Karp 해쉬 알고리즘 (문자에 대한 해쉬값을 비교할 때 적용할 수 있는 알고리즘)
- KMP 알고리즘
출처
'Algorithm > 리트코드(LeetCode)' 카테고리의 다른 글
| [LeetCode] Minimum Size Subarray Sum (1) | 2024.04.10 |
|---|---|
| [LeetCode] Two Sum II (0) | 2024.04.10 |
| [LeetCode] Add Binary (0) | 2024.04.08 |
| [LeetCode] Find Pivot Index (0) | 2024.04.08 |
| [LeetCode] Height Checker (0) | 2024.04.08 |
