String Matching

<aside>

• 3가지 알고리즘 존재
  • Naive
  • DFA(Deterministic Finite Automaton)
  • KMP(Knuth, Morris, Pratt)
• 위에서 가장 빠른 알고리즘은 KMP, 만약 합이 작은 경우면 DFA 알고리즘이 더 좋을 수 있음 </aside>

Naive

<aside>

• 한칸씩 이동하면서 단순 비교를 반복하는 가장 직관적인 알고리즘
• Text의 모든 자리마다 match가 되도록 가장 길게 놓을 수 있는 pattern의 앞부분 길이를 계산 해야함

예시

• 3행이 pattern이라고 가정할 때, 위의 7이 써있는 d의 경우 d 앞의 6글자 또한 패턴과 일치
• 가장 길게 놓을 수 있는 앞부분의 길이가 7이 되며 패턴과 일치하는 부분을 찾음

구현

Code

</aside>

DFA

<aside>

• Naive 알고리즘에서 각 숫자에 대한 표기를 더한 방식
• 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고 그 이후로도 일치할 경우 +1 씩 증가시켜 표기
• 만약 표기하려는 수가 이미 표기된 수보다 작으면 표기 불가
• 예시
  • abcabcd 문자열에서 abcd를 찾는 경우
    • 문자열 : abcabcd
    • 표시 숫자 :1231234

구현

Code

</aside>

KMP

<aside>

</aside>