Algorithm

KMP(Knuth-Morris-Pratt) algorithm 문자열 중 특정 패턴을 찾아내는 문자열 검색 알고리즘 중 한가지 연산량을 최대한 줄이기 위해 접두사와 접미사의 개념을 활용하여 jump하는 기법 > string length : N, pattern length

임의의 수 N에 대해 N의 약수들 중 $$\\sqrt{N}$$ 이하인 약수로 $$\\sqrt{N}$$ 이상인 약수를 구할 수 있다.그러므로 N의 전체 약수를 찾기 위해 $$O(N)$$이 아닌 $$O(\\sqrt{N})$$의 시간 복잡도를 갖을 수 있다.수학적 증명 참고