문자열 찾기2

• 

  문자열 찾기(매칭)_라빈 카프 알고리즘 [2/2] [ 라빈 카프 알고리즘이란? ] 찾을 문자열을 해쉬(hash)값으로 변환하여 문자열을 찾음 ※ 해쉬(해시, hash) - 특정 규칙을 이용해 데이터를 하나의 값으로 변경한 값을 의미 - 데이터의 일부분만 바껴도 해쉬값이 변경됨 - 낮은 확률로 다른 데이터가 같은 해쉬값으로 표현될 수도 있음 - 해쉬의 중복 확률이 낮을 수록 좋은 규칙이라고 할 수 있음 예를 들어 이번 라빈 카프 알고리즘에서 사용할 가장 간단한 해쉬값은 아래와 같이 만들 수 있습니다. "각 문자의 아스키코드"에 "2^자릿수" 를 곱해주고 그 합을 해쉬값으로 지정해주는 방식입니다. 현재 "abab"의 해쉬값은 1,465입니다. 중간에 문자가 하나 바뀌거나 같은 문자라도 자릿수가 다르면 모두 다른 값이 되는 것을 알 수 있습니다. ​ 문자가 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.

• 

  문자열 찾기(매칭)_KMP알고리즘 [1/2] [ KMP 알고리즘이란? ] 문자열의 가장 앞부분과 동일한 문자열 정보를 배열로 만들어 효율성을 검색의 높이는 방법 모두 다른 문자로 이루어진 문자라 하더라도 검색 효율성이 더 높음​ 개념 이해가 잘 안돼서 한참 고민했습니다. 사전에 유의해야 할 사항은 만약 "ababab"라는 문자열에서 "abab"를 찾는다고 했을 때, 2개가 검색이 돼야 한다는 점입니다. 하나만 검색되면 틀린 로직입니다. [ 일반 로직 ] 일반적인 로직 입니다. 먼저 첫 글자가 같으면 비교를 시작합니다. 끝까지 같지 않고 다른 글자가 나오면 다시 앞으로 이동해서 반복합니다. 만약 여기서 i가 그 자리에서 계속 전진만 하면 아까 "ababab"에서 "abab"를 찾을 경우 처음 네 글자 하나밖에 찾을 수가 없게 됩니다. 따라서 i의 위.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9.