문자열 찾기

wonjoogu·2021년 3월 22일
0

SSAFY TIL

목록 보기
6/18
  • 매 위치마다 패턴길이 만큼 비교하니까 시간 복잡도는 O(MN)인데

  • 패턴 매칭에 사용되는 알고리즘: 라빈-카프 알고리즘 / 보이어-무어 알고리즘 / KMP 알고리즘

  • 고지식한 알고리즘(Brute Force) : 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일히 비교하는 방식으로 동작

  • KMP(Knuth-Morris-Pratt Algorithm)

  • 패턴 안에 반복적인 형태를 보이면 유리

  • 패턴과 비교하다가 패턴 불일치가 발생하면 실패함수(배열: 패턴 불일치 발생하면 패턴 포인터인 j가 어느위치로 돌아갈지 지시해주는 역할)를 봐라! 실패함수가 가라는 위치로 가라!

  • 시간 복잡도 : O(M + N)

profile
SSAFY 5th

0개의 댓글