KMP에 적합한 패턴은 무엇이며 그 이유는 무엇입니까?

Question

다음 중 KMP 알고리즘과 관련하여 더 나은 성능을 보이는 두 가지 패턴 중 어느 것입니까?

패턴 1 = PQRSTUV 패턴 2 = PPPPPPP

Answer 1

우리가 이가지 경우

경우 1을 고려해야합니다 (이 존재하는 텍스트의 패턴 1의 접두사)

패턴 1과 패턴 2는 같은 수의 비교를 제공합니다.

사례 2

여기 또한 패턴 1과 패턴 2가 동일한 비교 수를 제공 (본문에 패턴 (2)의 프리픽스가 존재한다).

그래서 패턴 1과 패턴 2는 모두 같은 방식으로 실행됩니다.