\n \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4 \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc6b0\ub9ac\ub294 \ubb38\uc790\uc5f4 \ub0b4\uc5d0\uc11c \ud2b9\uc815 \ud328\ud134\uc774 \uc874\uc7ac\ud558\ub294\uc9c0 \ud655\uc778\ud558\uace0, \n \ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \ubc29\ubc95\uc740 \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4\uacfc \ucc3e\uace0\uc790 \ud558\ub294 \ud328\ud134\uc758 \ubaa8\ub4e0 \uc870\ud569\uc744 \ube44\uad50\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \n \ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \ubc29\ubc95\uc740 \uac04\ub2e8\ud558\uc9c0\ub9cc \ube44\ud6a8\uc728\uc801\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. KMP \uc54c\uace0\ub9ac\uc998\uc740 \n KMP \uc54c\uace0\ub9ac\uc998\uc740 ‘\ubd80\ubd84 \uc77c\uce58 \ud14c\uc774\ube14(\ub610\ub294 \uc2e4\ud328 \ud568\uc218)’\uc744 \ud65c\uc6a9\ud558\uc5ec \ubb38\uc790\uc5f4 \uac80\uc0c9\uc744 \n \ubd80\ubd84 \uc77c\uce58 \ud14c\uc774\ube14\uc744 \uc0dd\uc131\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4. \uc774 \ud14c\uc774\ube14\uc740 \uc774\uc804\uae4c\uc9c0 \n \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \ubb38\uc790\uc5f4 \ucc3e\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \ub450 \uac00\uc9c0 \uc54c\uace0\ub9ac\uc998, \n \ubb38\uc790\uc5f4 \ucc3e\uae30\uc640 \uad00\ub828\ub41c \ubb38\uc81c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c, \ub2e4\uc591\ud55c \uc608\uc81c\ub97c \ud480\uc5b4\ubcf4\uba70 <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"text<\/code>\uc640 \ucc3e\uace0\uc790 \ud558\ub294 \ubb38\uc790\uc5f4 pattern<\/code>\uc774 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc774\ub54c text<\/code> \ub0b4\uc5d0\uc11c pattern<\/code>\uc774 \uac00\uc7a5 \ucc98\uc74c\uc73c\ub85c \ub098\ud0c0\ub098\ub294 \uc704\uce58\ub97c
\n \ubc18\ud658\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc138\uc694. \ub9cc\uc57d pattern<\/code>\uc774 text<\/code> \ub0b4\uc5d0 \uc874\uc7ac\ud558\uc9c0 \uc54a\ub294\ub2e4\uba74 -1\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.\n <\/p>\n\uc785\ub825 \uc608\uc2dc<\/h3>\n
\n
\ucd9c\ub825 \uc608\uc2dc<\/h3>\n
\n
\ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n
\n \uc874\uc7ac\ud55c\ub2e4\uba74 \uadf8 \uc2dc\uc791 \uc778\ub371\uc2a4\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \ubb38\uc790\uc5f4 \ud0d0\uc0c9\uc740 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc774 \uc788\uc9c0\ub9cc,
\n \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uac00\uc7a5 \uae30\ubcf8\uc801\uc774\uace0 \uc9c1\uad00\uc801\uc778 \ubc29\ubc95\uc778 ‘\ube0c\ub8e8\ud2b8 \ud3ec\uc2a4(Brute Force)’ \ubc29\ubc95\uacfc
\n \uc880 \ub354 \ud6a8\uc728\uc801\uc778 ‘KMP(\uce74\ub77c\uce20\ubc14-\ubaa8\ub9ac\uc140)’ \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.
\n \uba3c\uc800 \ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \ubc29\ubc95\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n\ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \uc811\uadfc\ubc95<\/h3>\n
\n \uc774 \ubc29\ubc95\uc740 \uac04\ub2e8\ud558\uace0 \uc774\ud574\ud558\uae30 \uc27d\uc9c0\ub9cc, \ucd5c\uc545\uc758 \uacbd\uc6b0 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uac00 O(n*m)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c n\uc740
\n \ud14d\uc2a4\ud2b8\uc758 \uae38\uc774, m\uc740 \ud328\ud134\uc758 \uae38\uc774\uc785\ub2c8\ub2e4.\n <\/p>\n\uc54c\uace0\ub9ac\uc998 \ub2e8\uacc4<\/h4>\n
\n
\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc \uad6c\ud604<\/h4>\n
\nfunction findFirstOccurrence(text, pattern) {\n const n = text.length;\n const m = pattern.length;\n\n for (let i = 0; i <= n - m; i++) {\n let j;\n for (j = 0; j < m; j++) {\n if (text[i + j] !== pattern[j]) {\n break;\n }\n }\n if (j === m) {\n return i; \/\/ \ud328\ud134\uc774 \ubc1c\uacac\ub41c \uacbd\uc6b0\n }\n }\n return -1; \/\/ \ud328\ud134\uc774 \uc874\uc7ac\ud558\uc9c0 \uc54a\uc74c\n}\n\n\/\/ \ud14c\uc2a4\ud2b8 \uc608\uc2dc\nconsole.log(findFirstOccurrence(\"hello world\", \"world\")); \/\/ 6\nconsole.log(findFirstOccurrence(\"hello world\", \"abc\")); \/\/ -1\n <\/code><\/pre>\nKMP \uc54c\uace0\ub9ac\uc998<\/h2>\n
\n \uac80\uc0c9 \uc911\uc5d0 \ubd88\ud544\uc694\ud55c \uc7ac\uac80\uc0ac\ub97c \ubc29\uc9c0\ud558\uc5ec \uc131\ub2a5\uc744 \uac1c\uc120\ud569\ub2c8\ub2e4. KMP \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ubcf8 \uac1c\ub150\uc740
\n ‘\ud328\ud134\uc758 \uc77c\ubd80\uac00 \ub9e4\uce6d\ub420 \ub54c, \ub098\uba38\uc9c0 \ubd80\ubd84\uc744 \uc7ac\uc0ac\uc6a9’\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\nKMP \uc54c\uace0\ub9ac\uc998 \uc6d0\ub9ac<\/h3>\n
\n \ucd5c\uc801\ud654\ud569\ub2c8\ub2e4. \uc774 \ud14c\uc774\ube14\uc740 \uac80\uc0c9 \uc911 \uce90\uc2dc\ud560 \uc218 \uc788\ub294 \uc815\ubcf4\ub97c \uc81c\uacf5\ud569\ub2c8\ub2e4.
\n KMP \uc54c\uace0\ub9ac\uc998\uc740 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uac00 O(n + m)\uc73c\ub85c, \uc774\ub807\uac8c \ud5a5\uc0c1\ub41c \uc131\ub2a5\uc744 \ubcf4\uc5ec\uc8fc\ubbc0\ub85c
\n \ud070 \ub370\uc774\ud130\uc14b\uc5d0 \ub300\ud574\uc11c \uc720\uc6a9\ud569\ub2c8\ub2e4.\n <\/p>\n\uc54c\uace0\ub9ac\uc998 \ub2e8\uacc4<\/h4>\n
\n
\n \ud328\ud134\uc758 \uc704\uce58\ub97c \uc9c0\uc815\ud569\ub2c8\ub2e4.<\/li>\n\ubd80\ubd84 \uc77c\uce58 \ud14c\uc774\ube14 \uc0dd\uc131<\/h4>\n
\n \uac80\uc0ac\ud588\ub358 \ubb38\uc790\uc5f4\uc5d0\uc11c \ub3d9\uc77c\ud55c \uc811\ub450\uc0ac\uc640 \uc811\ubbf8\uc0ac\ub97c \uae30\ubc18\uc73c\ub85c \ud558\uc5ec \ub2e4\uc74c \ube44\uad50 \uc2dc
\n \uc778\ub371\uc2a4\ub97c \uc870\uc815\ud558\ub294 \ub370 \uc0ac\uc6a9\ub429\ub2c8\ub2e4.\n <\/p>\n\nfunction buildKMPTable(pattern) {\n const m = pattern.length;\n const lps = new Array(m).fill(0);\n let len = 0; \n let i = 1;\n\n while (i < m) {\n if (pattern[i] === pattern[len]) {\n len++;\n lps[i] = len;\n i++;\n } else {\n if (len !== 0) {\n len = lps[len - 1];\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n return lps;\n}\n <\/code><\/pre>\nKMP \uc54c\uace0\ub9ac\uc998 \ucf54\ub4dc \uad6c\ud604<\/h4>\n
\nfunction KMPSearch(text, pattern) {\n const n = text.length;\n const m = pattern.length;\n const lps = buildKMPTable(pattern);\n let i = 0; \/\/ \ud14d\uc2a4\ud2b8 \uc778\ub371\uc2a4\n let j = 0; \/\/ \ud328\ud134 \uc778\ub371\uc2a4\n\n while (i < n) {\n if (pattern[j] === text[i]) {\n i++;\n j++;\n }\n if (j === m) {\n return i - j; \/\/ \ud328\ud134\uc744 \ucc3e\uc74c\n } else if (i < n && pattern[j] !== text[i]) {\n if (j !== 0) {\n j = lps[j - 1];\n } else {\n i++;\n }\n }\n }\n return -1; \/\/ \ud328\ud134\uc744 \ucc3e\uc9c0 \ubabb\ud568\n}\n\n\/\/ \ud14c\uc2a4\ud2b8 \uc608\uc2dc\nconsole.log(KMPSearch(\"hello world\", \"world\")); \/\/ 6\nconsole.log(KMPSearch(\"hello world\", \"abc\")); \/\/ -1\n <\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\n \ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \ubc29\ubc95\uacfc KMP \uc54c\uace0\ub9ac\uc998\uc758 \uad6c\ud604 \ubc29\ubc95\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4.
\n \ube0c\ub8e8\ud2b8 \ud3ec\uc2a4 \ubc29\ubc95\uc740 \uc9c1\uad00\uc801\uc774\uace0 \uac04\ub2e8\ud558\uc9c0\ub9cc, \ud070 \ubb38\uc790\uc5f4\uc744 \uac80\uc0c9\ud560 \ub54c\ub294 \ube44\ud6a8\uc728\uc801\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ubc18\uba74 KMP \uc54c\uace0\ub9ac\uc998\uc740 \ub354\uc6b1 \ud6a8\uc728\uc801\uc73c\ub85c \ud328\ud134\uc744 \uac80\uc0c9\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744 \uc81c\uacf5\ud569\ub2c8\ub2e4.
\n \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub294 \uc774\ub7ec\ud55c \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud558\uace0 \uc801\uc808\ud558\uac8c \ud65c\uc6a9\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.\n <\/p>\n
\n \uacbd\ud5d8\uc744 \uc313\ub294 \uac83\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud559\uc2b5\ud558\uc5ec
\n \uc5ed\ub7c9\uc744 \ub354\uc6b1 \ud5a5\uc0c1\uc2dc\ucf1c\ubcf4\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n