{"id":59,"date":"2010-04-17T21:36:34","date_gmt":"2010-04-18T06:36:34","guid":{"rendered":"\/blog\/?p=59"},"modified":"2023-09-21T09:41:21","modified_gmt":"2023-09-21T00:41:21","slug":"en-wikipedia-org-wiki-kmp-%eb%84%a4%eb%b9%84%eb%b2%84-kmp-%ec%95%8c%ea%b3%a0%eb%a6%ac%ec%a6%98","status":"publish","type":"post","link":"https:\/\/hasu0707.duckdns.org\/blog\/?p=59","title":{"rendered":"en.wikipedia.org\/wiki\/KMP & [\ub124\ube44\ubc84] KMP \uc54c\uace0\ub9ac\uc998"},"content":{"rendered":"\n

KMP String Matching Algorithm\uc740<\/FONT><\/P>\n

 <\/P>\n

Knuth-Morris-Pratt\uc758 \uc57d\uc790\uc785\ub2c8\ub2e4..<\/FONT><\/P>\n

 <\/P>\n

\uc608\ub97c \ub4e4\uc5b4\ubcfc\uae4c\uc694.<\/FONT><\/P>\n

 <\/P>\n

abcabca         : \uae38\uc774 L<\/FONT><\/P>\n

abc                 : \uae38\uc774 M<\/FONT><\/P>\n

 <\/P>\n

abcabca\uc5d0\uc11c abc\uc758 \uac1c\uc218\ub294 \uba87\uac1c\uc77c\uae4c\uc694?<\/FONT><\/P>\n

 <\/P>\n

\uc885\uc885 \uc6b0\ub9ac\uac00 \ud558\ub294 \ubc29\ubc95\uc774 \uc77c\uc77c\ud788 \uae38\uc774 L\uc5d0 \ub300\ud574\uc11c M\uc744 \ucad9 \ub2e4 \ubcf4\ub294\uac70\uc8e0.<\/FONT><\/P>\n

 <\/P>\n

\uc6b0\ub9ac\uac00 \ud558\ub294 \ubc29\ubc95\uc774 \uc2dc\uac04\ubcf5\uc7a1\ub3c4 O(LM)\uc785\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uadf8\ub7f0\ub370 KMP\ub97c \uc774\uc6a9\ud558\uba74 O(L)\uc5d0 \uc774\uac83\uc744 \uad6c\ud560\uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

 <\/P>\n

\uc6b0\uc120 KMP String Matching\uc5d0\ub294 Pi \ubc30\uc5f4\uc774 \uc788\ub294\ub370, \uc774\uac83\uc744 \uba3c\uc800 \ubbf8\ub9ac \ub9cc\ub4e4\uc5b4\ub193\uc544\uc57c O(L)\uc5d0 \ud574\uacb0\uac00\ub2a5\ud569\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

Pi \ubc30\uc5f4\uc758 \uc815\uc758\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

Pi[i] : <\/FONT><\/P>\n

\uc704\uc5d0\uc11c [abc]\uc640 \uac19\uc774 \uac1c\uc218\ub97c \uc54c\uace0\uc790 \ud558\ub294 \ub300\uc0c1\uc5d0 \ub300\ud574\uc11c \uace0\ub824\ud560 \ub54c,<\/FONT><\/P>\n

\uadf8 \ub300\uc0c1\uc774 1 ~ i\uae4c\uc9c0 \uc2a4\ud2b8\ub9c1\uc774 \uc874\uc7ac\ud560 \ub54c, \uc811\ubbf8\uc0ac\uc640 \uc77c\uce58\ud55c \ucd5c\uc7a5 \uc811\ub450\uc0ac\uc758 \ub05d\uc790\ub9ac \uc704\uce58<\/FONT><\/P>\n

                                    (\ub2e8, Pi[i] \u2260 i)<\/U><\/STRONG><\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

 <\/P>\n

\uc608\ub97c \ub4e4\uc5b4\uc11c, ababaca\ub77c\ub294 \ubc30\uc5f4\uc774 \uc788\ub2e4\uace0 \uac00\uc815\ud574 \ubd05\uc2dc\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uc774 \ubc30\uc5f4\uc758 Pi[5]\ub294 3\uc785\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uc65c 3\uc774 \ub098\uc624\ub294\uc9c0 \ubcfc\uae4c\uc694.<\/FONT><\/P>\n

 <\/P>\n

Pi\uc758 \uc815\uc758\uc5d0\uc11c \"1 ~ i\uae4c\uc9c0 \uc2a4\ud2b8\ub9c1\uc774 \uc874\uc7ac\ud560 \ub54c\"\ub77c\uace0 \ud588\uc73c\ubbc0\ub85c<\/FONT><\/P>\n

 <\/P>\n

ababa\uc5d0 \ub300\ud574\uc11c \uace0\ub824\ud574\uc57c \ud569\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

ababa\uc5d0\uc11c, \uc811\ubbf8\uc0ac\uc640 \uc77c\uce58\ud55c \ucd5c\uc7a5 \uc811\ub450\uc0ac\ub294 aba\uc785\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uc811\ubbf8\uc0ac aba\uc640 \uc811\ub450\uc0ac aba\uac00 \uc77c\uce58\ud558\uc9c0\uc694.<\/FONT><\/P>\n

 <\/P>\n

\uc885\uc885 ababa\uc5d0\uc11c \uc811\ubbf8\uc0ac\uc640 \uc77c\uce58\ud55c \ucd5c\uc7a5\uc811\ub450\uc0ac\ub294 \uc790\uc2e0, ababa\uac00 \uc544\ub2c8\ub0d0.. \ub77c\uace0 \ud558\ub294\ub370<\/FONT><\/P>\n

 <\/P>\n

\uc704\uc758 \uc870\uac74\uc5d0 Pi[i] \u2260 i<\/U><\/STRONG>\ub77c\uace0 \uad75\uac8c \uc368\ub193\uc558\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

 <\/P>\n

\uc774\uc81c \uc774\uac83\uc774 \uc65c O(L + M)\uc5d0 \uc791\ub3d9\ud558\ub294\uc9c0 \ud655\uc778\ud574\ubcfc\uae4c\uc694.<\/FONT><\/P>\n

(M : \uba87\ubc88 \ub098\uc624\ub294\uc9c0 \uc54c\uace0\uc2f6\uc5b4\ud558\ub294 \ub300\uc0c1\uc758 \uae38\uc774.)<\/FONT><\/P>\n

 <\/P>\n

ababaabcbab\uc5d0\uc11c ababaca\uc758 \uac1c\uc218\ub97c \uc54c\uace0 \uc2f6\ub2e4\uace0 \ud574\ubd05\uc2dc\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

a b a b a a <\/FONT><\/U><\/STRONG>b c b a b           <\/FONT><\/P>\n

a b a b a c <\/FONT><\/U><\/STRONG>a<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

a b a b a\uae4c\uc9c0 \uc798 \ub098\uac00\ub2e4\uac00 \ubc11\uc904 \uce5c a\uc640 c\uc5d0\uc11c \ub2ec\ub77c\uc9c0\uc8e0.<\/FONT><\/P>\n

\uc5ec\uae30\uc11c \ub300\uac1c KMP\ub97c \ubaa8\ub974\uc2dc\ub294 \ubd84\ub4e4\uc774 \uad6c\ud604\ud558\ub294 \ubc29\ubc95\uc774 ababaca\ub97c \uc55e\uc73c\ub85c \ud55c\uce78 \ub561\uae30\ub294\uac83\uc778\ub370, \uc774\uac83\uc740 \uc2dc\uac04\ub0ad\ube44\ub77c\ub294 \uac83\uc774\uc8e0.<\/FONT><\/P>\n

 <\/P>\n

a b a b a<\/FONT> a <\/FONT><\/U><\/STRONG>b c b a b           <\/FONT><\/P>\n

a b a b a<\/FONT> c <\/FONT><\/U><\/STRONG>a<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

\uc5ec\uae30\uc11c \ubd89\uc740 \uc0c9\uc73c\ub85c \ub41c \ubd80\ubd84\uc744 \ubd05\uc2dc\ub2e4.<\/FONT><\/P>\n

ababa\uc5d0\uc11c \ub4a4 aba\uc640 \uc77c\uce58\ud55c \uc811\ub450\uc0ac\uc758 \uc704\uce58\ub294? Pi[5] = 3\uc774\ubbc0\ub85c '3' \uc785\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\ub530\ub77c\uc11c Pi[5]\ub97c \ud638\ucd9c\ud558\uba74, \uc544\ub798\uc640 \uac19\uc774 \ub429\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

a b a b a<\/FONT> a <\/FONT><\/U><\/STRONG>b c b a b           <\/FONT><\/P>\n

      <\/FONT>a b a<\/FONT> b <\/STRONG><\/U><\/FONT>a c <\/FONT>a<\/FONT><\/FONT><\/P>\n

 <\/P>\n

\uc5ec\uae30\uc11c \uc55e\uc758 aba \ubd80\ubd84\uc740 \uace0\ub824\ud574 \uc904 \ud544\uc694\uac00 \uc5c6\ub294\uac83\uc774<\/FONT><\/P>\n

Pi \ubc30\uc5f4\uc758 \uc815\uc758\ub97c \ubcf4\uba74 \uc811\ubbf8\uc0ac\uc640 \uac19\uc740 \ucd5c\uc7a5 \uc811\ub450\uc0ac\uac00 \uc800\uc7a5\ub418\uc5b4\uc788\ub294 \ubc30\uc5f4\uc774\ubbc0\ub85c<\/FONT><\/P>\n

\uc5b4\ucc28\ud53c aba\ub294 \uc704 \ubc30\uc5f4 aba\uc640 \uac19\ub2e4\ub294 \uac83\uc785\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uc5ec\uae30\uc11c \ub610 a\uc640 b\uac00 \uac19\uc740 \uc9c0 \ubd05\ub2c8\ub2e4.<\/FONT><\/P>\n

\ub2e4\ub974\uc8e0? \uadf8\ub807\ub2e4\uba74 \uc774\uc81c Pi[3]\uc744 \ud638\ucd9c\ud569\ub2c8\ub2e4. Pi[3] = 1\uc774\uaca0\uc8e0.<\/FONT><\/P>\n

 <\/P>\n

a b a b a<\/FONT> a <\/FONT><\/U><\/STRONG>b c b a b           <\/FONT><\/P>\n

           <\/FONT>a<\/FONT> b<\/FONT> <\/U>a<\/FONT><\/FONT> b a c a<\/FONT><\/FONT><\/FONT><\/P>\n

 <\/P>\n

\uc5ec\uae30\uc11c \uc55e\uc758 a\ub294 \uace0\ub824\ud574\uc904 \ud544\uc694\ub294 \uc5c6\uc2b5\ub2c8\ub2e4. \uc65c\ub0d0\ud558\uba74 \uc811\ubbf8\uc0ac\uc640 \uc77c\uce58\ud55c \ubd80\ubd84\uc774\uae30 \ub54c\ubb38\uc774\uc8e0.<\/FONT><\/P>\n

\ub2e4\uc2dc a\uc640 b\ub97c \ube44\uad50\ud574\uc90d\ub2c8\ub2e4. \ub2e4\ub984\uc744 \uc54c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

Pi[1] = 0\uc774\ubbc0\ub85c \uc774\uc81c \uc544\ub798 \ubc30\uc5f4\uc740 \uc55e\uc758 ababa\uc758 \uad74\ub808(?)\uc5d0\uc11c \uc644\uc804\ud788 \ubc97\uc5b4\ub098\uac8c \ub429\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

\uc774\ub7f0 \uc2dd\uc73c\ub85c \uc804\uc9c4\uc2dc\ucf1c\ub098\uac00\ub2e4\ubcf4\uba74 O(L+M)\uc5d0 \uac00\ub2a5\ud568\uc744 \uc54c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

\uadf8\ub807\ub2e4\uba74, Pi \ud568\uc218\ub294 \uc5b4\ub5bb\uac8c \uad6c\ud558\ub0d0.. \uc774\uac8c \uad00\uac74\uc774\uaca0\uc8e0.<\/FONT><\/P>\n

\uc774 \ubd80\ubd84\uc740 \uac04\ub2e8\ud558\ubbc0\ub85c \uc544\ub798 \uc758\uc0ac\ucf54\ub4dc\ub97c \ucc38\uace0\ud558\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\ucc38\uace0\uc801\uc73c\ub85c, \ucc45\uc740 Introduction to algorithms second edition \uc6d0\uc11c\ub97c \ucc38\uace0\ud588\uc2b5\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

\uc5ec\uae30\uc11c P\ub294 pi \ubc30\uc5f4\uc744 \ub9cc\ub4e4\uace0\uc790 \ud560 \ub54c \uadf8 \ub300\uc0c1 String\uc744 \ub9d0\ud569\ub2c8\ub2e4.<\/FONT><\/P>\n

 <\/P>\n

 <\/P>\n

 <\/P>\n

m \u2190 length[ P ]<\/FONT><\/P>\n

pi[1]  \u2190 0<\/FONT><\/P>\n

k \u2190 0<\/FONT><\/P>\n

 <\/P>\n

for q \u2190 2 to m<\/FONT><\/P>\n

   do while k > 0 and P[k + 1] \u2260 P[q]<\/FONT><\/P>\n

            do k \u2190 pi[k]<\/FONT><\/P>\n

        if P[k + 1] = P[q]<\/FONT><\/P>\n

            then k \u2190 k + 1<\/FONT><\/P>\n

        pi[q] \u2190 k<\/FONT><\/P>\n

 <\/P>\n

return pi \n<\/FONT>\n<\/FONT>\n","protected":false},"excerpt":{"rendered":"

KMP String Matching Algorithm\uc740   Knuth-Morris-Pratt\uc758 \uc57d\uc790\uc785\ub2c8\ub2e4..   \uc608\ub97c \ub4e4\uc5b4\ubcfc\uae4c\uc694.   abcabca         : \uae38\uc774 L abc                 : \uae38\uc774 M   abcabca\uc5d0\uc11c abc\uc758 \uac1c\uc218\ub294 \uba87\uac1c\uc77c\uae4c\uc694?   \uc885\uc885 \uc6b0\ub9ac\uac00 \ud558\ub294 \ubc29\ubc95\uc774 \uc77c\uc77c\ud788 \uae38\uc774 L\uc5d0 \ub300\ud574\uc11c M\uc744 \ucad9 \ub2e4 \ubcf4\ub294\uac70\uc8e0.   \uc6b0\ub9ac\uac00 \ud558\ub294 \ubc29\ubc95\uc774 \uc2dc\uac04\ubcf5\uc7a1\ub3c4 O(LM)\uc785\ub2c8\ub2e4. […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[18],"tags":[],"class_list":["post-59","post","type-post","status-publish","format-standard","hentry","category-development_language"],"_links":{"self":[{"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/59","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=59"}],"version-history":[{"count":0,"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/59\/revisions"}],"wp:attachment":[{"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=59"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=59"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hasu0707.duckdns.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=59"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}