idea

<aside> 💡 Hash 함수를 사용해 패턴 문자열과 텍스트 문자열의 부분 문자열을 비교하는 것

</aside>

• 첫 번째 M 자리의 나머지를 구한 다음부터 한 자리씩만 추가하면서 계산
• 간단한 계산으로 나머지를 구할 수 있어 빠른 문자열 탐색이 가능해짐.

특징

• 문자열을 숫자값으로 바꾼 다음 Hash 값을 계산하여 매칭하는 알고리즘

• 평균적으로 선형에 가까운 빠른 속도를 가짐.

  → but, 최악의 경우 $O(MN) = O(N^2)$ 의 시간 복잡도를 가짐.

⭐ Hornor’s Method

Hornor’s Method란,

• 다항식을 빠르고 효율적으로 평가하기 위한 알고리즘.
• 주어진 다항식을 계산할 때 필요한 곱셈의 횟수를 줄여, 계산의 복잡도를 크게 감소시킴.

기본 원리

• 일반적인 다항식

  $[P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0]$

• 다항식을 아래와 같이 재배열 하여 계산함.

  $[P(x) = (...((a_nx + a_{n-1})x + a_{n-2})x + \cdots + a_1)x + a_0]$

• 각 항을 계산할 때마다 이전에 계산한 결과에 (x)를 곱하고 새로운 계수를 더하는 방식으로 진행됨./

Example 1)

$$ P(x) = 2x^2 + 3x + 4 $$

1st. $P(x) = ((2)x + 3)x + 4)$