String Matching
- 단어를 찾아라
Naive Algorithm
- 한칸씩 밀면서 모든 글자를 다 비교함 O(MN)
- 여기서 패턴 길이만큼 다 비교안하고 다른글자나오면 다음 위치로 미는 식으로 할 수 있음
- 패턴의 길이와 j가 같아지면 종료
- 위에서 한칸씩 비교하다 다른 글자가 나오면 시작위치를 뒤로 돌리는걸 roll-back이라고 하는데 이게 없어야 시간을 줄일 수 있음
DFA(Deterministic Finite State Automaton)
- 하나의 state에서 특정 문자가 왔을때 갈수 있는 다른 state가 단 1개로 명확하기 때문에 Deterministic이라 함
- 0에서 A가오면 1로, 6에서 B가오면 4번으로
- 선이 없으면 무조건 처음으로 가는식으로 그림 간소화
- 이거는 DFA가 만들어졌다고 가정한것, 만들어져만 있으면 O(N), roll-back이없음
- DFA 사진 한장으로 요약
DFA Construction
- 위는 DFA가 만들어졌다고 가정 후 한것, DFA는 어떻게 만들것인가
- 미스매치가 일어난 지점(j라고하면)의 문자를 패턴의 1번부터 j-1까지 갔을때의 스태이트를 j가 왔을때의 위치임
- 스테이트에서 미스매치가 일어나면 1번 문자(BABA부터)를 스테이트 0번부터 돌려서 최종적으로 위치한 곳(X)에서 미스매치가 일어난 문자를 한번더 한 state가됨
- X위치(BABA해서 위치한 곳)을 매번 구하는게 아님
- 6번에서 미스매치되면 X의 위치는 0번 스테이트에서 BABA대신 BABAC를 한것 이전 X에서 한번만 더하면 됨
- X의 갱신은 이전 X에서 패턴의 그다음 글자 하나를 추가
- 일단 제일 왼쪽 초기화, 다음 줄은 이전 x번 줄을 복사(미스매치) 그 후 매칭되는 알파벳 갱신, x를 이전 x값에서 이번에 매칭된 알파벳을 넣는것으로 갱신
KMP
- prefix, suffix
- NULL과 전체 단어도 접두사,접미사에 해당됨
- 미스매치 후에 그 다음 시작위치를 그냥 틀린위치부터 하자는 아이디어
- 텍스트의 시작을 트린위치에서 하는거고 추가로 패턴매칭은 처음부터 안하고 패턴의 시작과, 이전에 매칭했던 곳에서 같은 부분은 건너띔
- 매칭하다 틀린 부분의 바로 앞을 기준으로 짜르고, 그것의 prefix, suffix가 겹치는 부분만큼 부터 다시 시작(0칸이나, 전체는 뺴고)
- 틀리면 텍스트는 롤백을 맥시멈 오버랩부터 하지만 매칭은 틀린곳부터 해도됨, 패턴은 맥시멈 오버롤의 길이의 다음 위치부터 매칭하면 됨
- fail펑션
- 패턴에서 실패한 위치에 따라 멕시멈 오버랩을 구하는 것
- 이거 할줄알기
KMU SW