[자료구조] String Matching

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다. String Matching string에서 내가 원하는 문자열을 찾는 방법을 말한다. 예를 들어 abababcabcabcdabccbaabdabcabcdabcd 라는 Text가 있다고 해보자. 우리는 이중에서 abcabcd 라는 pattern을 찾아야 한다. 수업시간에는 총 3가지 알고리즘을 알려주셨다. 1) Naive 2) DFA (Deterministic Finite Automaton) 3) KMP (Knuth, Morris, Pratt) 이중 가장 빠른 알고리즘은 KMP 알고리즘 이며, 만약 ∑가 작은경우라면 DFA알고리즘이 더 좋을 수 있다. (참고로 ∑는 알파벳의 집합을 의미한다, 예를 들어 ∑ &#..........

원문링크 : [자료구조] String Matching