DFA 알고리즘

4. DFA 알고리즘

Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 DFA 알고리즘 Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다. 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다. 만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다. abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다. 찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다. 이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다. 다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 ..