\n There is a given string \n To solve this problem, we need to check if a specific pattern exists within the string and, \n The Brute Force method compares all combinations of the given string and the pattern to be found. \n While the Brute Force method is simple, it can be inefficient. The KMP algorithm improves performance by \n The KMP algorithm optimizes string searching using a ‘partial match table (or failure function)’. \n The algorithm for creating the partial match table is as follows. This table is used to adjust \n In this tutorial, we explored two algorithms for solving the string search problem, \n Problems related to string searching are frequently featured in coding tests, so <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"text<\/code> and a string pattern<\/code> that needs to be found.
\n Write a function that returns the position where pattern<\/code> first appears in text<\/code>.
\n If the pattern<\/code> does not exist in text<\/code>, return -1.\n <\/p>\nInput Example<\/h3>\n
\n
Output Example<\/h3>\n
\n
Problem Solving Strategy<\/h2>\n
\n if it does, find its starting index. There are various algorithms for string searching, but
\n in this tutorial, we will use the most basic and intuitive method called ‘Brute Force’ and
\n a more efficient algorithm called ‘KMP (Knuth-Morris-Pratt)’.
\n Let’s first take a look at the Brute Force method.\n <\/p>\nBrute Force Approach<\/h3>\n
\n This method is simple and easy to understand, but in the worst case, its time complexity is O(n*m),
\n where n is the length of the text and m is the length of the pattern.\n <\/p>\nAlgorithm Steps<\/h4>\n
\n
JavaScript Code Implementation<\/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; \/\/ Pattern found\n }\n }\n return -1; \/\/ Pattern not found\n}\n\n\/\/ Test examples\nconsole.log(findFirstOccurrence(\"hello world\", \"world\")); \/\/ 6\nconsole.log(findFirstOccurrence(\"hello world\", \"abc\")); \/\/ -1\n <\/code><\/pre>\nKMP Algorithm<\/h2>\n
\n preventing unnecessary re-inspections during the search. The basic concept of the KMP algorithm is
\n ‘when part of the pattern matches, reuse the remainder’.\n <\/p>\nPrinciple of the KMP Algorithm<\/h3>\n
\n This table provides information that can be cached during the search.
\n The time complexity of the KMP algorithm is O(n + m), making it effective for large datasets.\n <\/p>\nAlgorithm Steps<\/h4>\n
\n
Creating the Partial Match Table<\/h4>\n
\n the index for the next comparison based on the same prefixes and suffixes from the previously examined string.\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 Algorithm Code Implementation<\/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; \/\/ Text index\n let j = 0; \/\/ Pattern index\n\n while (i < n) {\n if (pattern[j] === text[i]) {\n i++;\n j++;\n }\n if (j === m) {\n return i - j; \/\/ Pattern found\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; \/\/ Pattern not found\n}\n\n\/\/ Test examples\nconsole.log(KMPSearch(\"hello world\", \"world\")); \/\/ 6\nconsole.log(KMPSearch(\"hello world\", \"abc\")); \/\/ -1\n <\/code><\/pre>\nConclusion<\/h2>\n
\n the Brute Force method, and the KMP algorithm.
\n The Brute Force method is intuitive and straightforward but can be inefficient when searching large strings.
\n In contrast, the KMP algorithm provides a more efficient way to search for patterns.
\n Understanding and appropriately utilizing these diverse algorithms is important in real coding tests.\n <\/p>\n
\n it’s necessary to gain experience by solving various examples.
\n Keep learning different algorithm problems to further enhance your skills.\n <\/p>\n