\n \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4\uc5d0\uc11c \ud2b9\uc815 \ud328\ud134\uc758 \ubb38\uc790\uc5f4\uc774 \uba87 \ubc88 \ub4f1\uc7a5\ud558\ub294\uc9c0\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \n \ubb38\uc790\uc5f4 \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ubb38\uc790\uc5f4 \uac80\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4. \n \ubb38\uc790\uc5f4 \uac80\uc0c9 \ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ubc29\ubc95 \uc911 \ud558\ub098\ub294 KMP(Knuth-Morris-Pratt) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \n LPS \ubc30\uc5f4\uc740 \ud328\ud134 \ub0b4\uc5d0\uc11c \uc811\ub450\uc0ac\uc640 \uc811\ubbf8\uc0ac\uac00 \uc5bc\ub9c8\ub098 \uc77c\uce58\ud558\ub294\uc9c0\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ud328\ud134\uc744 \uc7ac\uc0ac\uc6a9\ud558\uba74\uc11c \uac80\uc0c9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\uc81c \uc704 \uacfc\uc815\uc744 \ubc14\ud0d5\uc73c\ub85c \ubb38\uc790\uc5f4 \ucc3e\uae30 \uc54c\uace0\ub9ac\uc998\uc744 \uc790\ubc14\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \n \uc704 \ucf54\ub4dc\ub294 KMP \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \uac83\uc73c\ub85c \ub450 \uac1c\uc758 \uc8fc\uc694 \ud568\uc218\uac00 \uc788\uc2b5\ub2c8\ub2e4. \n KMP \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n + m)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c n\uc740 \ud14d\uc2a4\ud2b8\uc758 \uae38\uc774, m\uc740 \ud328\ud134\uc758 \uae38\uc774\uc785\ub2c8\ub2e4. \n \uc624\ub298\uc740 \ubb38\uc790\uc5f4 \uac80\uc0c9 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c KMP \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \uc608\ub97c \ub4e4\uc5b4, \ubb38\uc790\uc5f4 \"banana\"<\/code>\uc5d0\uc11c \ud328\ud134 \"ana\"<\/code>\uac00 \uba87 \ubc88 \ub098\ud0c0\ub098\ub294\uc9c0\ub97c \uad6c\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n\uc785\ub825<\/h3>\n
\n
text<\/code>: \uac80\uc0c9\ud560 \uc804\uccb4 \ubb38\uc790\uc5f4 (1 \u2264 |text| \u2264 100,000)<\/li>\npattern<\/code>: \ucc3e\uc744 \ubb38\uc790\uc5f4 (1 \u2264 |pattern| \u2264 50)<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
text<\/code>\uc5d0\uc11c pattern<\/code>\uc774 \ub098\ud0c0\ub098\ub294 \ucd1d \ud69f\uc218\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.\n <\/p>\n\uc608\uc81c<\/h2>\n
\uc785\ub825<\/h3>\n
text = \"banana\"\npattern = \"ana\"<\/code><\/pre>\n\ucd9c\ub825<\/h3>\n
2<\/code><\/pre>\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n \uac00\uc7a5 \uac04\ub2e8\ud55c \ubc29\ubc95\uc740 \ubb38\uc790\uc5f4\uc744 \ud55c \uae00\uc790\uc529 \uc21c\ud68c\ud558\uba70 \ud328\ud134\uc744 \ube44\uad50\ud558\ub294 \ubc29\ubc95\uc774\uc9c0\ub9cc,
\n \uc774\ub294 \ud6a8\uc728\uc801\uc774\uc9c0 \uc54a\uc544 \ub300\uaddc\ubaa8 \ub370\uc774\ud130\uc5d0\uc11c \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uac00 O(n*m)\uc73c\ub85c \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.\n <\/p>\n\ud6a8\uc728\uc801\uc778 \ud574\uacb0\ucc45: KMP \uc54c\uace0\ub9ac\uc998<\/h3>\n
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ub450 \ubd80\ubd84\uc73c\ub85c \uad6c\uc131\ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n\n
LPS \ubc30\uc5f4 \uc0dd\uc131<\/h4>\n
\n \uc608\ub97c \ub4e4\uc5b4, \ud328\ud134\uc774 \"ABAB\"<\/code>\uc774\ub77c\uba74 LPS \ubc30\uc5f4\uc740 [0, 0, 1, 2]<\/code>\uc785\ub2c8\ub2e4.\n <\/p>\n\uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h4>\n
public class KMP {\n public static int[] computeLPS(String pattern) {\n int[] lps = new int[pattern.length()];\n int length = 0; \n int i = 1;\n \n while (i < pattern.length()) {\n if (pattern.charAt(i) == pattern.charAt(length)) {\n length++;\n lps[i] = length;\n i++;\n } else {\n if (length != 0) {\n length = lps[length - 1];\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n return lps;\n }\n\n public static int KMPsearch(String text, String pattern) {\n int[] lps = computeLPS(pattern);\n int i = 0; \n int j = 0; \n int count = 0;\n\n while (i < text.length()) {\n if (pattern.charAt(j) == text.charAt(i)) {\n i++;\n j++;\n\n if (j == pattern.length()) {\n count++;\n j = lps[j - 1];\n }\n } else {\n if (j != 0) {\n j = lps[j - 1];\n } else {\n i++;\n }\n }\n }\n return count;\n }\n\n public static void main(String[] args) {\n String text = \"banana\";\n String pattern = \"ana\";\n int result = KMPsearch(text, pattern);\n System.out.println(\"Substring Count: \" + result);\n }\n}<\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n computeLPS<\/code> \ud568\uc218\ub294 \ud328\ud134\uc5d0 \ub300\ud55c LPS \ubc30\uc5f4\uc744 \uc0dd\uc131\ud558\uace0, KMPsearch<\/code> \ud568\uc218\ub294 \ud14d\uc2a4\ud2b8\uc5d0\uc11c \ud328\ud134\uc744 \uac80\uc0c9\ud558\uba70 \uc77c\uce58\ud558\ub294 \uac1c\uc218\ub97c \uc138\ub294 \uc5ed\ud560\uc744 \ud569\ub2c8\ub2e4.\n <\/p>\n\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n \uc774\ub294 \ud328\ud134\uc774 \ud14d\uc2a4\ud2b8 \ub0b4\uc5d0\uc11c \uc774\ub3d9\ud558\uace0 \uc7ac\uc0ac\uc6a9\ub418\uae30 \ub54c\ubb38\uc5d0 \uac00\ub2a5\ud55c \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n\ub9c8\ubb34\ub9ac<\/h2>\n
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uba74 \ub2e4\uc591\ud55c \ubb38\uc790\uc5f4 \uac80\uc0c9 \ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ubb38\uc81c\ub97c \uc811\ud558\uba74\uc11c \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc2dc\ub3c4\ud574 \ubcf4\uc2dc\uace0 \uc2e4\ub825\uc744 \uc313\uc544\ubcf4\uc138\uc694!\n <\/p>\n