KMP 알고리즘, 기초, String Matching

챕터 : • 코딩테스트 String

[@HS-io3xp]

헐... kmp와 라빈카프 알고리즘이 9분만에 이해가됐어요. 설명 너무 잘하세요

[@짠-c4t]

kmp 알고리즘 최고의 설명입니다 ㅠㅠ

[@seonwookim5391]

좋은 강의 항상 감사드립니다!!

[@GrrrrB]

아....너무 좋은 설명 감사해요...ㅠㅠ

[@user-rx9ww4vr9u]

와 롤링해쉬 미쳤네요ㅋㅋ 이렇게쉬운방법이 있다니 hash짱

[@akkalee1207]

영상이 깔끔하네요! 영상에서 쓰인 그림판? 같은 툴은 이름이 뭔가요?

[@bnk159]

KMP 알고리즘 이해가 한번에 되었습니다 감사합니다!!

[@eezz_]

KMP, Rolling Hash 둘 다 처음 알게 된 정보인데 감사드립니다. 그냥 문제 푸는 것 보다 훨씬 재미있네요 ㅎㅎ 근데 롤링해시 같은 경우는 substring을 해싱 하는데, string 해싱은 시간 복잡도가 O(n)이 추가되지 않나요? substring이 짧으면 문제 없겠지만 길면, 최악 O(n^2) 될 것 같네요. KMP랑 롤링 해시랑 효율 비교를 해보려고 했는데, KMP 버퍼 구현이 좀 더 예제가 필요할 것 같아서 만들었는데 확인 부탁드립니다. a,b,c,a,b,d,a,b,a,b ,c,a,f 0,0,0,1,2,0,1,2,1,2,3,4,0 a,b,b,c,a,b,a,a,b,b,c,f 0,0,0,0,1,2,1,1,2,3,4,0 이게 맞다면 중간 a, a, b 부분이.. 일단 구현이 쉬운건 롤링 해시이고, KMP 방식이 성능이 더 좋아보이네여. 틀린 부분 항상 지적 부탁드립니다..^^

[@코드없는프로그래밍]

ys l님. 의견 감사합니다. 롤링 해쉬같은경우 그냥 string으로 잡고 hash를 만들게 되면 O(n^2)이 됩니다. 따라서 sliding window trick을 써야합니다. 이 트릭에는, 윈도우에 새로 알파벳이 들어오기전에 윈도우값의 자리수를 올려서 더함과 동시에, 빠지는 알파벳도 자릿수를 곱해줘서 빼주는 방법. 이경우는 substring의 길이가 길어지면 64bit제한을 넘어서게 되는 단점이 잇습니다. 그럴때는 각 알파벳의 헤시값을 슬라이딩 윈도우가 변할때마다 bit rotation을 해서 전체 XOR을 하는 방법. 그렇게 되면 윈도우에서 빠지는 방법은 그 알파벳의 hash값을 자릿수만큼 rotation씨킨뒤 다시 XOR을 시켜주면 됩니다. 글로 설명하기는 어려운데, 또 질문주세요.

[@eezz_]

@@코드없는프로그래밍 슬라이딩 윈도우 방식을 쓸 수 있나보네요, 뒤에 부분은 어렵지만 개발이 필요한 경우 참고하여 공부하겠습니다. 감사합니다!

[@kohy741]

아 선생님 질문있습니다 유튜브나 블로그 찾아보니깐 보통 해쉬함수를 아스키코드 값에 2의 제곱 수를 차례대로 곱하여 더해서 사용하던데 너무 코드가 막 난해하고 복잡해보이더라구요 그래서 그냥 (각 문자의 아스키코드의 합)%3 으로 하면 훨씬 이해하기 쉬울거같고 코드도 더 간단할거같은데 이렇게 바꿔도 상관없는거죠???

[@코드없는프로그래밍]

일단 이론적으로는 상관이 없습니다. 하지만 2의 제곱수를 곱하면서 해쉬값을 만들어가는 과정이 연산량이 적으면서 해쉬충돌이 적게나는 방법으로 알고있습니다. 말씀하신 아스키코드의합%3 같은경우는 일단 합을 통해 최종 해시값을 계산하기 때문에 충돌확률이 높아지고 마지막 mod 3 이 비싼 연산에 속합니다.

[@kohy741]

안녕하세요 선생님! 어제 array파트를끝내고 드디어 string 파트로 넘어왔는데 초반부터 되게 어렵군요! 하지만 해쉬함수를 좀 쉽게만들면 비교적 간단하게 풀수있을거같습니다! 암튼 근데 궁금한게 있는데요 이거 공부하다가 문득생각났는데요 제가 컨트롤 f 눌러서 키워드 검색하는걸 엄청 애용하거든요? 그럼 이 컨트롤 f눌러서 검색하는 기능은 KMP를 쓴건지 아니면 Rabin Karp(Rolling hash)를 쓴건지 궁금합니다!

[@코드없는프로그래밍]

그건 implementation 혹은 app마다 다를겁니다.

[@코드없는프로그래밍]

보통은 언어가 제공해주는 string.find함수를 쓰지않았을까 합니다.

[@cortana4572]

ㄱㅅ 영상보고 3분만에 이해했네요

[@건빵건빵-m7z]

코딩테스트 공부에 참고할만한 서적중에 한글 서적은 없을가요?

[@코드없는프로그래밍]

안녕하세요. 제가 해외에 거주하는 관계로 한글책은 잘 모릅니다. 원하시는 기업의 기출문제가 풍부하고 이해하기 쉬운책을 고르시면 될것입니다.

[@김준호-w3s]

영상 잘봤습니다! 질문이 있습니다. abcabd의 특정 패턴이 000120 이 되는 것에서 인덱스4 -> b의 패턴이 2가 되는 부분이 인덱스4 이전의 substr 중에서 찾고자하는 문자 b가 인덱스1에 있기 때문에 1+1 이 되어서 2가 된다 이해 제대로 한거겠죠? 이해를 제대로 한게 맞다면 아래의 예시는 제대로 구한 패턴이 맞는건가요? abcbaca -> 0002135 KMP 알고리즘을 최적화하기 위해서는 특정 패턴을 알아내는 것도 빠른 시간내로 해결해야 할 것 같은데 설명이 없어서 잠깐 생각해본바로는 현재 보고 있는 특정 문자에 대한 이전 사용여부 정보를 가지고 있는 1차원배열하나면 O(substr.size) 내로 구할 수 있을 것 같은데 이 방법을 사용해도 괜찮으려나요? 좀 더 빠른 방법이 있을까요?

[@코드없는프로그래밍]

안녕하세요. abcbaca 같은경우는 0000101이 됩니다. 찾고자 하는 문자 b를 찾는것이 아니라, 찾고자 하는 substring index 0부터 matching을 해줘야합니다. 두번째 질문은 이해가 되지 않는데, 주어진 string의 kmp pattern을 구하고자 한다면 이는 O(n) time complexity입니다.

[@namgiung]

abcabd 의 실패함수 값을 찾을 때, 영상 설명과 상관없이 이렇게 보시면 이해는 좀 편할 거 같습니다. (a)bcabd () 안에 있는 글자들의 접두사, 접미사 일치하는 가장 긴 길이를 찾는 거로 보시면 됩니다. (a)bcabd 은 0 입니다. 첫 번째는 0이라고 생각하시면 됩니다. (ab)cabd 는 접두사 a, 접미사 b 불일치하여 0 (abc)abd 는 일치하는 것 없으므로 0 (abca)bd 는 접두사 a 접미사 a 로 1 (abcab)d 는 접두사 ab 가 접미사 ab 와 일치하여 2 (abcabd) 는 일치하지 않으므로 0 abcabd 000120 abcbaca 를 같은 방법으로 하면 (a)bcbaca 0 (ab)cbaca 0 (abc)baca 0 (abcb)aca 0 (abcba)ca a 일치하여 1 (abcbac)a 0 (abcbaca) a 일치하여 1 abcbaca 0000101

[@김준호-w3s]

@@namgiung 감사합니다!!!! 어떤식으로 가는지 이해했어요. 자세한 답변감사합니다

[@hc-sc9mx]

와 좋은 질문 좋은 답변들 감사합니다~!

[@건빵건빵-m7z]

혹시 문자열의 해시값을 구하는 방법 관련해서 c++ 에서 관련 기능을 제공하는 함수가 있을가요?

[@코드없는프로그래밍]

안녕하세요. std::hash 를 찾아보시면 될듯합니다.

[@1dolcong]

5:20 에서 dabc... 이랑 abc가 첫번째에서 바로 미스매치 되버리는데 미스매치 될 때 한 칸 앞의 수를 보고 비교할 수를 결정 한다고 하셨는데 여기서 a가 첫번째라 앞에 가리키는 값이 없는데 참고 하지 않고 한 칸 올리는 것은 그냥 예외 사항이라 보고 올리신 건가요??

[@코드없는프로그래밍]

네 앞에 참조할것이 없기 때문에, 한칸 올리는 것입니다.

[@seonwookim5391]

혹시 leet code는 알고리즘 사이트에서의 위상은 어떤가요? 문제들 질이나 솔루션 등 잘 나와있나요?

[@코드없는프로그래밍]

코딩테스트 실전 준비에서는 1등이라고 생각합니다. 다양한 언어를 지원하고 어떠한 회사들이 최근에 어떤 문제를 얼마나 자주 출제하는지도 알 수 있습니다. 문제의 질은 기출문제이다 보니까 전체적으로는 준수합니다. 하지만 솔루션이 안좋은 경우가 있습니다. 문제의 양이 1600개 이상으로 방대합니다. 알고리즘 인터뷰/ 코딩테스트 자체가 모든 문제를 외우는 것이 아니라 필요한 DS/ALgorithm을 적용해서 푸는게 더 중요합니다. 때문에 코드없는 프로그래밍 채널에서 좋은 문제를 선정, 참고하여 다양한 Data Structure을 이용한 영상을 제작하고 있습니다. 감사합니다.

[@seonwookim5391]

감사합니다!

[@eezz_]

저도 leetcode 추천 동의합니다. 1. 최종 제출 시, 많은 예제 중에 틀린 부분의 input, 실제 결과값, 자신의 output이 잘 나와있어요. 이상한 input을 못 찾고 시간을 많이 뺏기는 경우가 없어서 좋아요. 다른 사이트는 제가 백준, 프로그래머스, 해커랭크 조금씩만 사용해봤는데... 해커랭크가 그나마 input을 알려줬던 것 같은데, 몇 개는 풀면 획득하는 coin으로 open할 수 있어요... 백준은 별로 안 해봤는데 include, main, cin, cout까지 작성이 필요합니다. 프로그래머스는 leetcode랑 비슷했는데 최종 제출 시, input이 안 나온 기억이 있네요. 2. 그리고 문제마다 discuss 게시판에 답이나 설명 영상 올려주신 분들이 많아요.. 좌절 가능. 3. submission 성공하면 자신의 성능, 메모리 다른 사람의 성능, 메모리 코드들을 볼 수 있어요. 더 많은 기능이 있겠지만 이 정도만 해도 제가 경험한 부분 중 최고인듯합니다.. leetcode로 공부하다가 실전 코딩 테스트를 할 때 그 회사의 코테 사이트에서 1~2주일 전에 연습하시면 될 거에요.

[@Jesus.Christ..]

이미 늦은 답글이긴 합니다만, 리트코드는 해외에서 필수에요. 그대로 내는 경우도 "매우" 많습니다.

[@유소정-l1j]

KMP 알고리즘에서 부분 문자열의 반복 패턴 index를 찾는 정확한 규칙이 뭔가요? 참고하려고 검색했을 때는 접두부, 접미부를 나눠서 동일한 지 비교하라고 하던대 헷갈리네요 ㅠ

[@코드없는프로그래밍]

같은 kmp 알고리즘이더라도 여러 implementation방법이 있습니다. 영상에서 보다시피 패턴 index라고 하지만 pass된 index로 부터 character match가 전부입니다. 감사합니다.

[@isaaclee3714]

선생님 소스 어디서 볼수 있을까요?

[@코드없는프로그래밍]

해당 챕터는 아직 code implementation이 마무리 되지 않았습니다. 최대한 빠른 시간내에 마무시 짓도록 하겠습니다.

[@Manas-co8wl]

실제로 stl 라이브러리에서 쓰이는 알고리즘일까요?

[@코드없는프로그래밍]

STL은 implementation detail을 정의하고 있지 않습니다. 하지만 libstdc++ 같은경우는 소스코드가 공개되어있기때문에 몇번의 구글링만 하시면 어떤 알고리즘을 사용하는지 알 수 있을겁니다. 단순히 생각하기에는 KMP를 사용하지는 않을것 같습니다만, 확실히 하고싶다면 꼭 확인하시기 바랍니다. 감사합니다.