\uc5ec\ub7ec\ubd84\uc740 \ubb38\uc790\uc5f4 S\uc5d0\uc11c \ud2b9\uc815 \ubb38\uc790\uc5f4 P\uac00 \uba87 \ubc88 \ub098\ud0c0\ub098\ub294\uc9c0\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \ubb38\uc790\uc5f4 P\ub294 \ubb38\uc790\uc5f4 S\uc5d0 \uc5ec\ub7ec \ubc88 \ub098\ud0c0\ub0a0 \uc218 \uc788\uc73c\uba70, \uacb9\uce58\ub294 \uacbd\uc6b0\ub3c4 \uc788\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4 S\uc758 \uae38\uc774\ub294 1 \uc774\uc0c1 100,000 \uc774\ud558\uc774\uba70, \ubb38\uc790\uc5f4 P\uc758 \uae38\uc774\ub294 1 \uc774\uc0c1 100 \uc774\ud558\uc785\ub2c8\ub2e4. \ub300\uc18c\ubb38\uc790\ub294 \uad6c\ubcc4\ud558\uc9c0 \uc54a\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubaa8\ub4e0 \ubc1c\uc0dd\uc758 \uc218\ub97c \uc815\uc218\ub85c \ucd9c\ub825\ud558\uc138\uc694.<\/p>\n
\n abCabcABCabc\n abc\n <\/pre>\n\ucd9c\ub825<\/h4>\n
\n 4\n <\/pre>\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1. \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n
\uc774 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4 S\uc5d0\uc11c \ubb38\uc790\uc5f4 P\uac00 \uba87 \ubc88 \ub4f1\uc7a5\ud558\ub294\uc9c0\ub97c \ud655\uc778\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \ubb38\uc790\uc5f4\uc774 \ub300\uc18c\ubb38\uc790\ub97c \uad6c\ubd84\ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0, \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub450 \ubb38\uc790\uc5f4 \ubaa8\ub450 \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\ud558\uc5ec \ube44\uad50\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
2. \uc811\uadfc \ubc29\ubc95<\/h3>\n
\ubb38\uc790\uc5f4 \uac80\uc0c9 \ubb38\uc81c\ub294 \uc5ec\ub7ec \uc811\uadfc \ubc29\ubc95\uc774 \uc788\uc9c0\ub9cc, \uc6b0\ub9ac\ub294 \uac04\ub2e8\ud55c \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc9c1\uc811\uc801\uc73c\ub85c \ud574\uacb0\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c\uacfc \uac19\uc740 \uc808\ucc28\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uac83\uc785\ub2c8\ub2e4:<\/p>\n
\n
- \ubb38\uc790\uc5f4 S\ub97c \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\ud569\ub2c8\ub2e4.<\/li>\n
- \ubb38\uc790\uc5f4 P\ub97c \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\ud569\ub2c8\ub2e4.<\/li>\n
- \ubc18\ubcf5\ubb38\uc744 \ud1b5\ud574 \ubb38\uc790\uc5f4 S\uc5d0\uc11c \ubb38\uc790\uc5f4 P\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uac01 \ubc1c\uc0dd \uc2dc \uce74\uc6b4\ud2b8\ub97c \uc99d\uac00\uc2dc\ud0b5\ub2c8\ub2e4.<\/li>\n<\/ol>\n
3. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h3>\n
\uc54c\uace0\ub9ac\uc998\uc758 \ubcf5\uc7a1\ub3c4\ub294 O(n*m)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c n\uc740 \ubb38\uc790\uc5f4 S\uc758 \uae38\uc774, m\uc740 \ubb38\uc790\uc5f4 P\uc758 \uae38\uc774\uc785\ub2c8\ub2e4. \ub450 \ubb38\uc790\uc5f4\uc744 \uc9c1\uc811 \ube44\uad50\ud558\uae30 \ub54c\ubb38\uc5d0, \ucd5c\uc545\uc758 \uacbd\uc6b0 \ubaa8\ub4e0 \uc778\ub371\uc2a4\uc5d0\uc11c \ubb38\uc790\uc5f4 P\ub97c \ud0d0\uc0c9\ud574\uc57c \ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
4. C# \ucf54\ub4dc \uad6c\ud604<\/h3>\n
\uc544\ub798\ub294 C# \ucf54\ub4dc \uc608\uc2dc\uc785\ub2c8\ub2e4.<\/p>\n
\n using System;\n\n class Program\n {\n static void Main(string[] args)\n {\n string S = Console.ReadLine();\n string P = Console.ReadLine();\n\n \/\/ \ub300\uc18c\ubb38\uc790\ub97c \uad6c\ubd84\ud558\uc9c0 \uc54a\uae30 \uc704\ud574 \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\n S = S.ToLower();\n P = P.ToLower();\n\n int count = 0;\n int position = 0;\n\n while ((position = S.IndexOf(P, position)) != -1)\n {\n count++;\n position++; \/\/ \uacb9\uce58\ub294 \uacbd\uc6b0\ub97c \uace0\ub824\ud558\uc5ec \uc704\uce58\ub97c \ud55c \uce78 \uc774\ub3d9\n }\n\n Console.WriteLine(count);\n }\n }\n <\/pre>\n5. \ucf54\ub4dc \uc124\uba85<\/h3>\n
\ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub97c \ud3ec\ud568\ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uc0ac\uc6a9\uc790\ub85c\ubd80\ud130 \ubb38\uc790\uc5f4 S\uc640 P\ub97c \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- \ubb38\uc790\uc5f4 S\uc640 P\ub97c \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\ud558\uc5ec \ube44\uad50\ub97c \uc6a9\uc774\ud558\uac8c \ud569\ub2c8\ub2e4.<\/li>\n
- while \ub8e8\ud504\ub97c \ud1b5\ud574 \ubb38\uc790\uc5f4 S\uc5d0\uc11c P\uc758 \uc704\uce58\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.<\/li>\n
- S.IndexOf() \uba54\uc11c\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud604\uc7ac \uc704\uce58\ubd80\ud130 P\uc758 \uc704\uce58\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. \ucc3e\uc740 \uc704\uce58\uac00 -1\uc774 \uc544\ub2cc \uacbd\uc6b0, \uce74\uc6b4\ud2b8\ub97c \uc99d\uac00\uc2dc\ud0a4\uace0 \ub2e4\uc74c \uc704\uce58\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.<\/li>\n
- \ubaa8\ub4e0 \ubc1c\uc0dd \uc218\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
\uc131\ub2a5 \uace0\ub824\uc0ac\ud56d<\/h2>\n
\uc774 \ucf54\ub4dc\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n*m)\uc774\uba70, \uc774\ub294 \ubb38\uc790\uc5f4 S\uc758 \uae38\uc774\uc640 P\uc758 \uae38\uc774\uc5d0 \ub530\ub77c \ub2ec\ub77c\uc9d1\ub2c8\ub2e4. \ub9cc\uc57d S\uc758 \uae38\uc774\uac00 100,000\uc774\uace0 P\uc758 \uae38\uc774\uac00 100\uc774\ub77c\uba74, \ucd5c\uc545\uc758 \uacbd\uc6b0 10,000,000 \uc5f0\uc0b0\uc774 \uc694\uad6c\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub294 \ub2e4\uc18c \ube44\ud6a8\uc728\uc801\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ub530\ub77c\uc11c, \ub9cc\uc57d \uc131\ub2a5\uc744 \ub354\uc6b1 \uac1c\uc120\ud558\uace0 \uc2f6\ub2e4\uba74 KMP(Knuth-Morris-Pratt) \uc54c\uace0\ub9ac\uc998\uacfc \uac19\uc740 \ubb38\uc790\uc5f4 \uac80\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uace0\ub824\ud574\ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4. KMP \uc54c\uace0\ub9ac\uc998\uc740 O(n + m)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uba70, \ub354 \ud6a8\uc728\uc801\uc778 \uac80\uc0c9\uc744 \uac00\ub2a5\ud558\uac8c \ud569\ub2c8\ub2e4.<\/p>\n
5-1. KMP \uc54c\uace0\ub9ac\uc998 \uac1c\uc694<\/h3>\n
KMP \uc54c\uace0\ub9ac\uc998\uc740 \ubd80\ubd84 \ubb38\uc790\uc5f4 \uac80\uc0c9\uc744 \uc704\ud55c \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc544\ub798\uc640 \uac19\uc740 \uc6d0\ub9ac\ub97c \uc774\uc6a9\ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uba3c\uc800, \ud328\ud134 \ubb38\uc790\uc5f4 P\uc758 \ubd80\ubd84 \uc77c\uce58\ub97c \uc800\uc7a5\ud558\ub294 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4.<\/li>\n
- \ubb38\uc790\uc5f4 S\ub97c \ud0d0\uc0c9\ud558\uba74\uc11c, \ub9cc\uc57d \ubd88\uc77c\uce58\uac00 \ubc1c\uc0dd\ud588\uc744 \ub54c \ud328\ud134 \ubb38\uc790\uc5f4\uc5d0\uc11c \uba87 \uac1c\uc758 \ubb38\uc790\ub97c \uac74\ub108\ub6f8 \uc218 \uc788\ub294\uc9c0\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
5-2. KMP \uc54c\uace0\ub9ac\uc998 C# \uad6c\ud604<\/h3>\n
\uc544\ub798\ub294 KMP \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c C# \ucf54\ub4dc\uc785\ub2c8\ub2e4.<\/p>\n
\n using System;\n\n class Program\n {\n static void Main(string[] args)\n {\n string S = Console.ReadLine();\n string P = Console.ReadLine();\n\n \/\/ \ub300\uc18c\ubb38\uc790\ub97c \uad6c\ubd84\ud558\uc9c0 \uc54a\uae30 \uc704\ud574 \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\n S = S.ToLower();\n P = P.ToLower();\n\n int count = KMP(S, P);\n Console.WriteLine(count);\n }\n\n static int KMP(string S, string P)\n {\n int m = P.Length;\n int n = S.Length;\n int count = 0;\n\n \/\/ LPS \ubc30\uc5f4 \ucd08\uae30\ud654\n int[] lps = new int[m];\n ComputeLPSArray(P, m, lps);\n\n int i = 0; \/\/ S\uc758 \uc778\ub371\uc2a4\n int j = 0; \/\/ P\uc758 \uc778\ub371\uc2a4\n\n while (i < n)\n {\n if (P[j] == S[i])\n {\n i++;\n j++;\n }\n\n if (j == m)\n {\n count++;\n j = lps[j - 1];\n }\n else if (i < n && P[j] != S[i])\n {\n if (j != 0)\n j = lps[j - 1];\n else\n i++;\n }\n }\n return count;\n }\n\n static void ComputeLPSArray(string P, int m, int[] lps)\n {\n int len = 0;\n int i = 1;\n lps[0] = 0;\n\n while (i < m)\n {\n if (P[i] == P[len])\n {\n len++;\n lps[i] = len;\n i++;\n }\n else\n {\n if (len != 0)\n len = lps[len - 1];\n else\n {\n lps[i] = 0;\n i++;\n }\n }\n }\n }\n }\n <\/pre>\n6. KMP \uc54c\uace0\ub9ac\uc998 \ucf54\ub4dc \uc124\uba85<\/h3>\n
\uc704 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uc808\ucc28\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uc6b0\uc120 \ubb38\uc790\uc5f4 S\uc640 P\ub97c \uc18c\ubb38\uc790\ub85c \ubcc0\ud658\ud569\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ub300\uc18c\ubb38\uc790 \uad6c\ubd84\uc744 \uc5c6\uc571\ub2c8\ub2e4.<\/li>\n
- KMP \uba54\uc11c\ub4dc\ub97c \ud638\ucd9c\ud558\uc5ec \ubb38\uc790\uc5f4 P\uac00 \ubb38\uc790\uc5f4 S\uc5d0 \uba87 \ubc88 \ub098\ud0c0\ub098\ub294\uc9c0\ub97c \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/li>\n
- KMP \uba54\uc11c\ub4dc \ub0b4\ubd80\uc5d0\uc11c LPS \ubc30\uc5f4\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4. LPS \ubc30\uc5f4\uc740 \ud328\ud134 P\uc758 \uc811\ub450\uc0ac\uc640 \uc811\ubbf8\uc0ac\uc758 \ucd5c\ub300 \uae38\uc774\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.<\/li>\n
- \ubb38\uc790\uc5f4 S\ub97c \uc2a4\uce94\ud558\uba74\uc11c \ud328\ud134 P\uc758 \ub9e4\uce6d\uc744 \uc9c4\ud589\ud569\ub2c8\ub2e4. \ub9e4\uce6d\uc774 \uc131\uacf5\ud558\uba74 \uce74\uc6b4\ud2b8\ub97c \uc99d\uac00\uc2dc\ud0a4\uace0, \ub9e4\uce6d\uc774 \uc2e4\ud328\ud558\uba74 LPS \ubc30\uc5f4\uc744 \ucc38\uc870\ud558\uc5ec \uc704\uce58\ub97c \uc870\uc815\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
\uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 C#\uc744 \uc774\uc6a9\ud558\uc5ec \ubb38\uc790\uc5f4\uc5d0\uc11c \ud2b9\uc815 \ubb38\uc790\uc5f4\uc744 \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uac04\ub2e8\ud55c \ubc18\ubcf5\ubb38\uc744 \uc774\uc6a9\ud55c \uc811\uadfc\ubd80\ud130 KMP \uc54c\uace0\ub9ac\uc998\uc73c\ub85c\uc758 \ud655\uc7a5\uae4c\uc9c0, \ubb38\uc790\uc5f4 \uac80\uc0c9 \ubb38\uc81c\uc5d0 \ub300\ud55c \uae30\ubcf8 \uac1c\ub150\uacfc \ud6a8\uc728\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc744 \ud559\uc2b5\ud560 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc5d0\uc11c \ub2e4\uc591\ud55c \ucf54\ub4dc \uad6c\ud604 \ubc29\uc2dd\uacfc \uc54c\uace0\ub9ac\uc998\uc758 \ubcf5\uc7a1\ub3c4\ub97c \uc774\ud574\ud558\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub418\uc5c8\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
\ucc38\uace0 \uc790\ub8cc<\/h2>\n