1. 부분문자열 검색 z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다. 이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자. 여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다. 이제 s에 대한 z-function을 계산하자. [0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다. 문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로, 이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다. 2. 연습문제 17..
1. brute force 패턴 매칭 알고리즘 원본 문자열 s에 대하여 특정 문자열 패턴 p가 몇번이나 존재하는지 찾고자 하는 알고리즘 모든 경우의 수를 검사하여 몇번이나 패턴이 존재하는지 검사한다 이때 패턴과 해당 길이의 부분 문자열을 전부 비교하는게 아니라 한글자 한글자씩을 비교함 예를 들어 s = abcdefghi p = cdf 라고 한다면 abcdefghi cdf 부터 비교를 시작.. abc와 cdf를 한번에 비교하는게 아니라 a와 c를 비교하여 a와 c가 다르므로 cdf를 한칸 뒤로 민다 내 생각에 abc와 cdf를 한번에 비교하는 시간보다 a와 c를 비교하고 한칸 뒤로 미는게 효과적이라 그런가?? 아닌데..? 일단 한글자씩 비교한다고 배웠으니까 그렇게 알아놓자고 아무튼 abcdefghi cdf..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
