String Matching
·
CS/Data Structure
Problem definition (문제 정의)text : simple string of characters (문자열을 찾을 텍스트)pattern : simple string of characters (찾을 텍스트 - 패턴)to do : find where in the text the patter occurs 패턴이 나타나는 텍스트 찾기AlgorithmAlgorithm시간공간naive \(O(mn)\) \(O(n)\) or \(O(1)\)DFA (Deterministic Finite Automaton) \(O(\sum m + n)\) - 테이블 제작 + 텍스트 읽기 \(O(\sum m\) - 테이블 메모리KMP (Knuth Morris Pratt) \(O(m+n)\) \(O(m)\)* n : 텍스트의 길..