# KMP 알고리즘

<figure><img src="/files/E8zyvcZNXZMKbuJRlkVo" alt=""><figcaption></figcaption></figure>

(실제로 문자열 검색 나오면 (gcc 아닐 땐) find() 쓰거나 rabin-karp(부분 문자열을 해시값으로 변환 후 해시값을 찾기) 쓰는게 편하다고 함)

실패 함수 (LPS)

* 시작부터의 접두사와 해당 인덱스부터의 접미사가 같은 가장 긴 길이
* 어디서 비교를 재시도 할지 기록해둔 값 (지금 비교를 실패한 문자열과 똑같은 앞의 문자열로 재도전)
* 실패 함수 생성에선
  * 값을 len이라는 변수에 담아두며 '새로 추가된 글자'의 idx와 비교할 위치를 결정한다
  * 새로운 글자가 비교 문자열과 달랐고, len!=0 이었다면, 재시도(길이를 줄이면 글자가 같아질지 확인)를 위해 len을 변경한다.
    * 이때 실패 함수의 값은 아직 결정되지 않은 채로 다음 while문 루프를 돌게 된다
  * len==0이면 더 이상 비교할 문자열이 없으니 0으로 기록하고 넘어간다
* KMP 비교에선
  * 실패 함수 생성과 본질적으로 같다
  * 글자가 다른데 len!=0이면 아직 코인이 남아있는 곳(동일한 문자열이 아직 존재하는 곳)으로 가서 새로운 글자를 다시 비교해본다.
  * O(m+n)인 이유는, i를 탐색할 전체 문자열 인덱스, j를 찾아낼 부분 문자열 인덱스라 할 때,
    * i가 올라갈 때 j도 한 번밖에 못 올라가기 때문이다.
    * 내려가는 것까지 최악으로 가정하면 최대 2m 이동 가능

{% content-ref url="/spaces/lgCmoOkHlzfuOQBbOsbg/pages/6L9fFizcvbxIYU2w6eSj" %}
[11585 속타는 저녁 메뉴](/note/main-page/algorithm/undefined-1/11585.md)
{% endcontent-ref %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/kmp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.