알고리즘(Algorithm)/문자열 (2) 썸네일형 리스트형 라빈 카프 문자열 매칭 알고리즘(Rabin-Karp String Matching Algorithm) 라빈 카프 문자열 매칭 알고리즘(Rabin-Karp String Matching Algorithm)은 문자열 S가 있고 찾으려는 패턴 P가 있을때 S문자열에 패턴 P가 있는지 없는지 문자(char)를 하나씩 비교하는 방식이아닌 해싱된 값을 비교하는 방식을 사용한다. 해싱이 무엇인지 잘 모르면 우선 해시테이블(Hash Table) 자료구조를 선행학습해야 한다. 그럼 해싱함수는 무엇이고 어떤 절차로 해싱값을 서로 비교하면서 문자열에 패턴이 있는지 확인할수 있을까? 해싱으로 비교하는 방법은 매우 심플한데 문자열 S와 패턴 P가 아래처럼 있다고 했을 때 문자열(S) = "THISISATESTTEXT" 패턴(P) = "TEST" P를 해싱한 Hp 값을 먼저 구하고 S문자열을 인덱스(i) = 0부터 순차적으로 증가.. 나이브 문자열 매칭 알고리즘 (Naive String match algorithm) 패턴 검색은 컴퓨터 과학에서 중요한 문제이다. 패턴 검색이 필요한 사례들은 매우 많은데 메모장, 파일, 브라우저 또는 데이터베이스에서 문자열을 검색 할 때 패턴 검색 알고리즘으로 검색 결과를 표시하는 것이 그 예이다. 문제는 매우 긴 문자열에서 내가 찾고자 하는 문자열(패턴)을 어떻게 빠르고 정확하게 찾아낼수 있을까? 이다. 문자열에서 패턴을 검색하기 위해 다양한 알고리즘들이 있는데 그 중 나이브 문자열 매칭 알고리즘 (Naive String match algorithm)은 문자열 처음부터 끝까지 우리가 찾고자 하는 패턴과 일치하는지 하나씩 비교해가면서 단순 무식하게 문자열을 찾는다. [출처] https://apprize.info/science/algorithms_2/7.html 예를들어 아래 표처럼 문.. 이전 1 다음
