라빈-카프 알고리즘 (Rabin-Karp) 라빈-카프 알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘입니다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 됩니다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 됩니다. 예를 들어 ABCD와 ABED라는 문자열이 있을 때 ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618 ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624 이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 됩니다. ..

KMP 알고리즘 (Knuth-Morris-Pratt) 일반적으로 어떤 문서나 파일에서 특정 문자열을 찾기 위해 Ctrl + F를 활용해 찾기를 시도합니다. 이러한 행위가 바로 문자열 탐색, 혹은 문자열 검색입니다. 문자열 검색은 다음과 같은 알고리즘에 의해 수행됩니다. A B C D E C D 결과 : 실패 검색을 당하는 문자열은 ABCDE 이며 검색하려는 문자열은 CD 입니다. ABCDE의 앞자리부터 검색할 문자열 CD를 하나씩 대조하며 탐색을 시작합니다. 일치하지 않으므로 한칸 이동합니다 A B C D E C D 결과 : 실패 역시 일치하지 않으므로 한칸 이동합니다. A B C D E C D 결과 : 일치 문자열이 일치하여 검색에 성공합니다. 만약 검색 당한 문자열이 ABCDEABCDE 처럼 길다면 ..