티스토리 뷰

알고리즘

KMP : 문자열 검색 알고리즘

bowbowbow 2016. 1. 17. 01:11

문자열 검색이 뭐지?



워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 

브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다.


아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한 것입니다. 본문에서 89개의 "테이프"를 찾았다고 순식간에 알려주네요.


이렇게 텍스트내(본문)에서 특정 문자열, 패턴("테이프")를 찾는 것을 문자열 검색이라고 부릅니다.

이 문자열 검색은 어떤 방식으로 구현되는걸까요?



가장 단순한 문자열 검색



먼저 가장 단순한 방법의 문자열 검색을 생각해봅시다.

텍스트 "ABCABABCDE"에서 패턴 "ABC"가 어디서 등장하는지 찾아봅시다.


패턴 "ABC"를 한자리씩 옮기면서 같은지 비교합니다.


같아?

 A

 A

 

 

 

 

 

 

 

->같아!


같아?

 A

 

A

B

 

 

 

 

 

 

->달라!


같아?

 A

 


A

B

C

 

 

 

 

 

->달라!


같아?

 A

 



A

B

C

 

 

 

 

->달라!


같아?

 A

 




 

 

 

->달라!


같아?

 A

 





B

C

 

 

->같아!


같아?

 A

 






A

B

 

->달라!


같아?

 A

 







A

->달라!


위와 같은 과정을 진행했을 때 

텍스트 "ABCABABCDEFAAAB"에서 패턴 "ABC"는 밑줄친 자리에서 총 두번 등장함을 알 수 있습니다.


ABCABABCDE


이 과정의 시간 복잡도는 텍스트의 길이를 N, 패턴의 길이를 M이라 할 때 각 텍스트의 인덱스에 대해 패턴이 일치하는지 비교하므로 O(NM)입니다.


이 보다 더 빠르고 효율적으로 하는 방법은 없을까요?

있습니다! KMP 알고리즘을 이용하면 O(N+M)에 문자열 검색을 할 수 있습니다.




KMP 알고리즘이란?



KMP알고리즘은 만든 사람이름이 Knuth, Morris, Prett이기 때문에 앞글자를 하나씩 따서 KMP알고리즘이라 이름 붙었습니다.

KMP알고리즘의 시간 복잡도는 O(N+M)으로 위의 무식한 방법 O(NM) 보다 매우 빠릅니다.


단순한 방법에서 개선할 수 있는 여지가 보이지 않는데요.. 도대체 무슨 짓을 하길레 이렇게 빠르게할 수 있을까요? 

그 비법을 파헤쳐봅시다.




먼저 알아야 하는 것



KMP 알고리즘을 이해하기 위해 먼저 알아야 하는 것이 2가지가 있습니다.


첫번째는 접두사(prefix)와 접미사(suffix)입니다.

직관적으로 "banana"의 접미사와 접두사를 보면 무엇인지 이해될 것 입니다.


<banana의 접두사>


b

ba

ban

bana

banan

banana


이 6개가 banana의 접두사(prefix) 입니다.


<banana의 접미사>

a

na

ana

nana

anana

banana


이 6개가 banana의 접미사(suffix) 입니다.


두번째로 pi배열 입니다.

pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이

(이때 prefix가 0~i  까지의 부분 문자열과 같으면 안된다.)


무슨 말인지 모르겠죠? 예시를 보면 직관적으로 이해할 수 있을 겁니다.


먼저 문자열 "ABAABAB"의 pi배열을 구해봅시다.

 i

부분 문자열 

 pi[i]

 0

A

 0

 1

AB 

 0

 2

ABA

 1

 3

ABAA

 1

 4

ABAAB

 2

 5

ABAABA

 3

 6

ABAABAB

 2


한번 더 "AABAA"의 pi배열을 구해봅시다.

 i

부분 문자열 

 pi[i]

 0

A

 0

 1

AA

 1

 2

AAB

 0

 3

AABA

 1

 4

AABAA

 2


이제 KMP알고리즘을 이해하기 위해 필요한 지식을 갖췄습니다!




단순한 방법은 정보를 낭비하고 있다!



위에서 설명한 단순한 방법은 진행과정 중에 발생한 멋진 정보를 낭비하고 있습니다.

어떤 정보를 낭비하고 있다는 걸까요?


텍스트 "ABCDABCDABEE"에서 패턴 "ABCDABE"를 찾는 상황을 생각해봅시다.


같니?

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C 

E

 패턴

 A 

B

 C

D 

A 

 B

 

 

 

 

 

->달라!

첫번째 시도에서 패턴의 0~5부분 문자열("ABCDAB")는 텍스트와 일치했지만 6번째 인덱스의 E가 텍스트와 일치하지 않았습니다.


단순한 방법은 그 후 두번째 시도에서 이렇게 진행합니다.

같니?

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C 

E

 패턴


A

B

C

D

A

B

 E

 

 

 

 

->달라!


첫번째 시도에서 두번째 시도로 넘어갈때 지금까지 발견한 멋진 정보를 사용하지 않았다는게 보이나요?


첫번째 시도에서 알게된건 아래 박스친 부분이 틀렸다는 사실만이 아닙니다.


또 알수있는 사실, 즉 지금까지 낭비하고 있었던 정보는 아래 박스친 부분은 일치한다는 사실입니다.

이 정보를 십분 활용해서 검색 속도를 개선하는것이 바로 KMP알고리즘의 핵심 비법입니다.





일치했다는 사실을 어떻게 활용할 것인가



위 정보를 활용한 결과 이 상태에서 

중간 시도를 껑충~! 건너띄고 


바로 아래 단계로 넘어갈 수 있습니다. (i는 텍스트의 현재 비교위치, j는 패턴의 현재 비교위치를 나타내는 변수입니다.)

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C (i) 

E

 패턴





A

B

C (j)

 


그게 가능한 이유는 일치했던 "ABCDAB"에서 파란색 박스로 표시한 접두사(prefix) AB와 접미사(suffix) AB가 일치하기 때문입니다. 또한 이것이 접두사와 접미사가 일치하는 최대 길이이기 때문입니다. 이 값이 바로 패턴 "ABCDABE"의 pi[5] =2 값입니다.


아래에 껑충 건너띈 단계를 자세히 나타냈습니다.


중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 5여야 했기 때문입니다.

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C 

E

 패턴


A

B

C

D

A

B

 

 

 

 


또 중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 4여야 했기 때문입니다.

 덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C 

E

 패턴



A

B

C

D

A

 

 

 



또 중간 단계인 아래 단계를 시도해볼 필요가 없습니다. 이 단계에서 패턴이 일치하려면 적어도 pi[5]= 3여야 했기 때문입니다.

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A 

B 

C 

E

 패턴




A

B

C

D

A

 

 



또 i는 텍스트의 현재 비교위치, j는 패턴의 현재 비교위치를 나타내는 변수일 때 i, j를 여기서 시작할 필요가 없습니다.

p[5] = 2라는 정보는 접미사 AB가 접두사 AB와 같다는 것을 말하므로 패턴 "ABCDABE"에서 "AB"는 이미 텍스트와 일치함을 알 수  있기 때문입니다.

 인덱스

0

10 

11 

 텍스트

A

B 

C 

D 

A (i)

B 

C 

E

 패턴





A (j)

B

C

D

A

B

 



이렇게 kmp 알고리즘은 틀렸다는 사실이 아니라 조금이라도 일치했었다는 정보에 주목하고 미리 전처리 해둔 pi배열을 이용해서 많은 중간 시도를 껑충 건너띌 수 있게 합니다.


지금까지 전반적인 kmp알고리즘의 원리를 살펴봤습니다. 이제 어떻게 kmp를 구현하는지 살펴봅시다.




KMP의 구현



kmp알고리즘의 

크게 주어진 패턴에 대해 pi배열을 얻는 getPi함수와 pi배열을 이용해 문자열 검색을 시행하는 kmp함수로 나누어 구현했습니다.


kmp 알고리즘을 전형적으로 사용하는 문제인 백준온라인저지 1786번 : 찾기 문제의 입출력에 대한 kmp알고리즘 코드를 작성하겠습니다.


(코드에 등장하는 auto 는 c++11에서 자료형을 자동으로 지정해주는 식별자입니다.)

위 코드에서 kmp함수와 getPi함수가 구체적으로 어떻게 작동하는지 설명하겠습니다.




kmp 함수 구현



저도 위 함수에서 6~7번 라인이 이해하기 어려웠습니다.

whlie(j>0 & s[i] != p[j])

j = p[j-1];

는 위에서 설명한 것 처럼 일치했던 정보와 pi배열을 이용해서 중간 단계를 껑충 뛰어넘는 부분입니다.

그런데 한 번만 j = p[j-1]해주면 될거 같은데 왜 while문 안에서 조건을 만족할 때 까지 반복되도록 했을까요?

그 이유는 주어진 정보로 최대한 중간 단계를 뛰어 넘기 위해서 입니다. 아래 예시를 보면서 이해합시다.


텍스트 : "ABABABABBABABABABC"에서 패턴 "ABABABABC"를 찾는 상황입니다.

왜 중간단계를 뛰어넘는것을 여러번 해야하는지 아례 예시로 나타냈습니다. i = 8일 때 while문 내부가 실행되는 모습입니다.


첫번째 시도에서 패턴의 마지막 문자가 일치하지 않았지만 "ABABABAB" 부분이 텍스트와 일치하여 pi[7] = 6값을 이용해 중간 단계를 점프합니다.

 인덱

 0

10 

11 

12 

13 

14 

15 

16 

17 

 텍스트

 A

B (i) 

 패턴

A

B

A

B

A 

B 

A 

B 

C (j) 

 

 

 

 

 

 

 

 

 


점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABABAB"가 일치하므로 pi[6]= 4를 이용해서 다시한번 점프할 수 있습니다. 

 인덱

 0

10 

11 

12 

13 

14 

15 

16 

17 

 텍스트

 A

B

B (i) 

 패턴



A

B

A 

B 

A 

B 

A (j) 

 B

 

 

 

 

 

 

 



점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABAB"가 일치하므로 pi[3]= 2를 이용해서 다시한번 점프할 수 있습니다. 

 인

 0

10 

11 

12 

13 

14 

15 

16 

17 

 텍스트

 A

B (i) 

 패턴





A 

B 

A 

B 

A (j)

 

 

 

 

 



또 점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 이제 pi[1] = 0이므로 다시 점프합니다.

 인덱스

 0

10 

11 

12 

13 

14 

15 

16 

17 

 텍스트

 A

B 

B (i)

 패턴





 

 

 A

B 

A (j)

 

 

 



다음 단계로 넘어갑니다. 다음과 같이 i가 증가해서 다음 스텝으로 넘어가고 j =0 이 되었습니다.

 덱스

 0

10 

11 

12 

13 

14 

15 

16 

17 

 텍스트

 A

A (i)

 패턴





 

 

 

 

 

 A (j)

C


while문 안을 제외한 부분은 위에서 설명한 부분을 통해 코드를 직접 읽으면서 이해하기 바랍니다.




getPi 함수 구현



getPi 함수는 kmp함수와 매우 유사하지 않나요?


먼저 getPi함수를 가장 단순한 방법으로 구현하면 Pi배열을 얻으려는 패턴의 길이를 m이라 할 때 O(m^3)의 시간이 필요합니다.

텍스트는 대부분 길지만 찾으려는 패턴의 길이는 대부분 짧기 때문에 m^3도 충분한 시간이지만 kmp의 원리를 Pi배열을 얻을 때도 사용하면

Pi배열 생성 시간을 O(m) 으로 비약적으로 시간을 단축할 수 있습니다.

위 코드는 O(m) 시간복잡도를 가지는 코드입니다. 


먼저 패턴 "ABABABAC"의 Pi배열의 생성 과정을 쭉 나열해보겠습니다.


P[1]과 P[0]이 일치하지 않아서 Pi[1] = 0이 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0







 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

1 (i)

 4

 

 

 

 

 

 

 

 

 

값 

B

 A

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 

0 (j)

1

2

3

4

5

6

 

 

 

 

 

 

 

 

 값

 

 B

 

 

 

 

 

 

 

 


P[2]와 P[0]가 일치해서 P[2] = 1이 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1






 

 

 

 

 

 

 

 

 

패턴

P

인덱스 

 0

2 (i)

 4

 

 

 

 

 

 

 

 

 

값 

B 

 A

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0 (j)

1

2

3

4

5

6

 

 

 

 

 

 

 

 값

 


A

A

B

A

B

 

 

 

 

 

 

 


P[3]와 P[1]가 일치해서 P[3] = 2가 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2





 

 

 

 

 

 

 

 

 

패턴

P

인덱스 

 0

3 (i) 

 4

 

 

 

 

 

 

 

 

 

값 

 A

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0

1 (j)

2

3

4

5

6

 

 

 

 

 

 

 

 값

 


A

B 

A

B

A

B

 

 

 

 

 

 

 


P[4]와 P[2]가 일치해서 P[4] = 3가 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3




 

 

 

 

 

 

 

 

 

패턴

P

인덱스 

 0

 4 (i)

 

 

 

 

 

 

 

 

 

값 

 A

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0

1

2 (j)

3

4

5

6

 

 

 

 

 

 

 

 값

 


A

B 

A

B

A

B

 

 

 

 

 

 

 



P[5]와 P[3]가 일치해서 P[5] = 4가 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4



 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

 4

5 (i)

 

 

 

 

 

 

 

 

 

값 

 A

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0

1

2

3 (j)

4

5

6

 

 

 

 

 

 

 

 값

 


A

B 

A

B

A

B

 

 

 

 

 

 

 



P[6]와 P[4]가 일치해서 P[6] = 5가 저장됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5


 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

 4

5

6 (i)

 

 

 

 

 

 

 

 

 

값 

 A

B 

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0

1

2

3

4 (j)

5

6

 

 

 

 

 

 

 

 값

 


A

A

B

A

B

 

 

 

 

 

 

 



P[7]와 P[5]가 불 일치해서 j를 j = Pi[4] 을 대입해 j 인덱스를 앞으로 당깁니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5


 

 

 

 

 

 

 

 

 

패턴

P

인덱스 

 0

 4

5

6

7 (i)

 

 

 

 

 

 

 

 

 

값 

 A

B 

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 


0

1

2

3

4

5 (j)

6

 

 

 

 

 

 

 

 값

 


A

A

B

A

B

 

 

 

 

 

 

 



P[7]와 P[3]이 또 불 일치해서 j를 j = Pi[2] 을 대입해 j 인덱스를 앞으로 당깁니다. 즉 중간단계를 pi배열을 이용해 점프합니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5


 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

 4

5

6

7 (i)

 

 

 

 

 

 

 

 

 

값 

 A

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 




0

1

2

3 (j)

4

 6

 7

 

 

 

 

 

 값

 




A

B

A

B

B

 

 

 

 

 



P[7]와 P[1]이 또 불 일치해서 j를 j = Pi[0] 을 대입해 j 인덱스를 앞으로 당깁니다.  즉 중간단계를 pi배열을 이용해 점프합니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5


 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

 4

5

6

7 (i)

 

 

 

 

 

 

 

 

 

값 

 A

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 






0

1 (j)

2

4

5

 

 

 

 값

 






A

B

A

B

A

B

 A

 C

 

 

 



P[7]와 P[0]이 또 불 일치해서 j는 인덱스 0으로 그대로 유지됩니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5

0

 

 

 

 

 

 

 

 

 

패턴

P

인덱스 

 0

 4

5

6

7 (i)

 

 

 

 

 

 

 

 

 

값 

 A

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 







0 (j)

1

3

4

5

6

 

 

 값

 







A

B

A

B

A

B

A

 

 



i가 패턴의 길이 7보다 커져서 종료합니다.

 Pi

 인덱스

 0

 2

 3

 4

 5

 7

 

 

 

 

 

 

 

 

 

 값

 0

1

2

3

4

5

0

 

 

 

 

 

 

 

 

 

패턴

인덱스 

 0

 4

5

6

 8 (i)

 

 

 

 

 

 

 

 

값 

 A

A 

 

 

 

 

 

 

 

 

 

패턴

 인덱스

 








0 (j)

1

2

3

4

5

6

 

 값

 








A

B

A

B

A

B

 



위 과정을 통해 Pi배열을 구할 때도 kmp원리를 이용한 것을 확인할 수 있습니다.


댓글
  • 이전 댓글 더보기
  • 프로필사진 케케 감사합니다. 이해가 잘 되었어요!! 2017.03.23 15:38
  • 프로필사진 aaass 감사합니다!!근데 while문 조건에 j>0은 왜필요한지 알려주실수있을까요..? ㅜㅜ 죄송합니다 이해력이 좀 부족해서 2017.03.28 19:07
  • 프로필사진 BlogIcon bowbowbow while(j > 0 && p[i] != p[j]) {
    j = pi[j-1];
    }
    이 부분이 글에서 설명하는 "일치했던 정보를 이용해서 점프"하는 것을 구현한 부분이에요

    이 때 "한 글자 라도 일치한 것"이 있어야 "그 정보를 이용해서 점프"를 할 수 있을텐데

    j>0 조건이 "한 글자 라도 일치한 것이 있냐"를 확인하는 조건이에요 !

    2017.03.29 22:01 신고
  • 프로필사진 북극곰괴력 갓멍멍... 당신은 대체... 2017.07.31 12:02
  • 프로필사진 두둠칫 갓멍멍.... 차근차근 설명해주심에 이해가 팍팍 되네요 ㅎㅎ 2017.08.21 10:20
  • 프로필사진 북극곰괴력 점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABABAB"가 일치하므로 pi[6]= 4를 이용해서 다시한번 점프할 수 있습니다.

    여기서 pi[6]=4가아니라 pi[5]=4인것같아요.
    좋은글 항상 잘읽고있습니다.
    2017.08.30 11:32
  • 프로필사진 갓승원 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ승워이~ 2017.09.27 01:24
  • 프로필사진 컴소공 역시..정리가 너무 잘 되어있어서 정말 좋아요 정말 감사합니다! 2017.11.20 20:53
  • 프로필사진 감사합니다 감사합니다 진짜 kmp이해 하나도 안됐는데 이거 보면서 아! 라는 단어가 나왔네요 진짜 감사합니다!!! 2017.11.21 21:24
  • 프로필사진 큰돌 잘보았습니다. ㅎ 저 질문이 있는데요 왜 string p 의 pi배열을 찾을 때 m^3 시간복잡도가 되는 것인가요? ㅇ 2018.02.02 05:17
  • 프로필사진 ㅜㅜ 알고리즘 시험보기 4시간 전에 이 글을 봤네요..
    영어로 된 피피티를 보다가 포기할까 싶었는데
    혹시몰라 검색하길 잘했습니다ㅠㅠㅠ
    넘나 쉽게 정리해주셔서 감사합니다 ㅠㅠㅠㅠㅠㅠㅠㅠ
    2018.12.11 12:15
  • 프로필사진 ㅇㅇ 찾아본거중에서 가장 이해가 잘되네요 감사합니다 2018.12.16 16:58
  • 프로필사진 kmp 함수에서 i-m+1의 의미를 잘 모르겠습니다 ㅠㅠㅠ 2019.02.22 14:26
  • 프로필사진 이주연 최고네요. 2019.03.29 00:39
  • 프로필사진 JMKanmo 감사합니다. 2019.04.24 22:03
  • 프로필사진 ㅇㅇ 정성이 대단하세요 bb 2019.05.26 11:22
  • 프로필사진 박찬준 글 잘 읽었습니다!!! 2019.06.04 20:42
  • 프로필사진 질문 패턴 "ABABABABC" 에서 pi[7] 이면 "ABABABAB" 까지의 접두사가 접미사와 같을 때 최대길이니까 4가 되어야하는거아닌가요.. 2019.06.15 01:54
  • 프로필사진 cy 접두사와 접미사가 겹쳐도 됩니다.
    pi[7] = 6 이라는건
    "ABABAB"로 접두사와 접미사가 같다는 의미입니다.
    2019.09.11 14:58
  • 프로필사진 제이훈 kmp함수 설명하는 부분에서
    "점프하자 마자 바로 텍스트 i번째 인덱스와 패턴 j번째 인덱스가 일치하지 않습니다. 여기서 하지만 패턴 "ABABAB"가 일치하므로 pi[6]= 4를 이용해서 다시한번 점프할 수 있습니다. "
    -> 이부분 pi[6]=4가 아닌 pi[5]=4 아닌가요? 글만 보고 이해한거라 확신이 들진 않네요..
    2019.10.28 13:35
  • 프로필사진 쿠케캬캬 와.. 글 몇개씩 찾아보다가 이거 몇시간 들여다보고 드디어 이해했네요.. 진짜 정리너무 잘되어있습니다. 감사합니다 2020.01.16 17:26
  • 프로필사진 codenstory Tag에서 KMP는 Knuth-Morris-Prett이 아니라 Knuth-Morris-Pratt 아닌가요? 2020.02.03 21:50
  • 프로필사진 ??? Knuth-MungMungMung-Pratt 입니다 2020.03.15 03:15
댓글쓰기 폼