코딩하기 좋은 밤 코딩하기 좋은 밤

dfa

• [알고리즘] String Matching

  SW/Algorithm 2018. 1. 6. 05:30

  스트링 매치 코드링크 브로트포스 : 한 칸씩 옮기면서.. 매칭 O(m*n) m=패턴 / n=스트링 DFA KMP algorithm DFA (Deterministic Finite Automaton) 시작 스테이트 - accept 스테이트. 패턴에 알맞는 단어가 나오면 다음 스테이트. 내부적으로는 이차원 배열을 사용(1에서 A나오면 2번으로..) DFA construction x를 구한다. x = [들어온단어][전스테이트의 x] 이다. x는 그 다음스테이션의 기본값으로 세팅하면 된다. [들어온단어][스테이트]위치에 다음 스테이트 값(i+1)을 넣는다. 반복.. (마지막은 넣지않는다.) int x=0;for(int i=0;i AAA, AABB => null) 미스매치시 이부분을 다시 사용한다.AAABBAAAC..

  Read More