{"id":33632,"date":"2024-11-01T09:18:46","date_gmt":"2024-11-01T09:18:46","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33632"},"modified":"2024-11-01T11:47:20","modified_gmt":"2024-11-01T11:47:20","slug":"python-coding-test-course-string-search","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33632\/","title":{"rendered":"Python Coding Test Course, String Search"},"content":{"rendered":"<div class=\"post\">\n<p>Hello! Today, we will discuss a string search problem to prepare for coding tests. String search problems are fundamentally algorithmic challenges that involve finding specific patterns or substrings within a string. It is important to test efficiency, accuracy, and various methodologies to enhance understanding of how to approach coding test scenarios.<\/p>\n<h2>Problem Description<\/h2>\n<p>You are given a string <code>s<\/code> and a string <code>t<\/code>, and you need to write a function to calculate how many times the string <code>t<\/code> appears in the string <code>s<\/code>. Note that the string <code>t<\/code> can overlap.<\/p>\n<p><strong>Example Input:<\/strong><\/p>\n<pre>\n    s = \"abababab\"\n    t = \"aba\"\n    <\/pre>\n<p><strong>Example Output:<\/strong><\/p>\n<pre>\n    4\n    <\/pre>\n<h2>Approach to the Problem<\/h2>\n<p>To solve this problem, the following approaches can be used:<\/p>\n<ul>\n<li><strong>Sliding Window Method<\/strong>: You can explore the string while moving like a sliding window.<\/li>\n<li><strong>String Search Algorithms<\/strong>: You can use string search algorithms like KMP.<\/li>\n<\/ul>\n<h2>Sliding Window Approach<\/h2>\n<p>Let me explain how to solve this problem using the sliding window method. This method can provide a simple yet efficient solution.<\/p>\n<p>The basic idea of the sliding window method is to traverse the given string <code>s<\/code> and compare it with the string <code>t<\/code> at each position. The approximate steps are as follows:<\/p>\n<ol>\n<li>Initialize a variable <code>count<\/code> to store the number of patterns found.<\/li>\n<li>Run a loop over each index of the string <code>s<\/code>.<\/li>\n<li>In each iteration, take a substring from the current index of <code>s<\/code> of length <code>len(t)<\/code>.<\/li>\n<li>Compare the obtained substring with <code>t<\/code>.<\/li>\n<li>If they match, increment <code>count<\/code>.<\/li>\n<li>After traversing all indices of the string <code>s<\/code>, return <code>count<\/code>.<\/li>\n<\/ol>\n<h2>Python Code Implementation<\/h2>\n<p>Based on the above approach, let&#8217;s write Python code:<\/p>\n<pre><code>\ndef count_occurrences(s, t):\n    count = 0\n    t_len = len(t)\n    s_len = len(s)\n\n    for i in range(s_len - t_len + 1):\n        if s[i:i + t_len] == t:\n            count += 1\n\n    return count\n\n# Example Test\ns = \"abababab\"\nt = \"aba\"\nresult = count_occurrences(s, t)\nprint(\"Occurrences of '{}' in '{}': {}\".format(t, s, result))\n    <\/code><\/pre>\n<h2>Time Complexity Analysis<\/h2>\n<p>The above code has a time complexity of O(n * m), where n is the length of string <code>s<\/code>, and m is the length of string <code>t<\/code>. However, this implementation can have worse performance due to simple string comparisons.<\/p>\n<h2>Solution Using the KMP Algorithm<\/h2>\n<p>In addition to the sliding window method, you can use the KMP algorithm to solve this problem more efficiently. The KMP algorithm is a linear time algorithm that searches the string only once to find pattern matches. The key of this algorithm is to precompute the information about prefixes and suffixes of the pattern to help advance the pattern when there is a mismatch.<\/p>\n<h3>Basic Steps of the KMP Algorithm<\/h3>\n<ol>\n<li>Create the LPS (Longest Prefix Suffix) array for the pattern <code>t<\/code>.<\/li>\n<li>Traverse the string <code>s<\/code> while referring to the LPS array to determine how many positions to skip in case of character mismatch.<\/li>\n<li>Track all pattern matches.<\/li>\n<\/ol>\n<h3>Function to Generate LPS Array<\/h3>\n<p>To generate the LPS array, we can write the following function:<\/p>\n<pre><code>\ndef compute_lps(pattern):\n    length = 0\n    lps = [0] * len(pattern)\n    i = 1\n\n    while i < len(pattern):\n        if pattern[i] == pattern[length]:\n            length += 1\n            lps[i] = length\n            i += 1\n        else:\n            if length != 0:\n                length = lps[length-1]\n            else:\n                lps[i] = 0\n                i += 1\n    return lps\n    <\/code><\/pre>\n<h3>KMP Algorithm Implementation<\/h3>\n<p>Now, let's write the actual string search code based on the KMP algorithm:<\/p>\n<pre><code>\ndef kmp_search(s, t):\n    lps = compute_lps(t)\n    count = 0\n    i = 0  # Index of string s\n    j = 0  # Index of pattern t\n\n    while i < len(s):\n        if s[i] == t[j]:\n            i += 1\n            j += 1\n\n        if j == len(t):\n            count += 1\n            j = lps[j-1]\n        elif i < len(s) and s[i] != t[j]:  # Match failure\n            if j != 0:\n                j = lps[j-1]\n            else:\n                i += 1\n\n    return count\n\n# Example Test\ns = \"abababab\"\nt = \"aba\"\nresult = kmp_search(s, t)\nprint(\"Occurrences of '{}' in '{}': {}\".format(t, s, result))\n    <\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>Today, we solved the string search problem using both the sliding window method and the KMP algorithm. The sliding window method is intuitive and simple, while the KMP algorithm offers a more efficient approach. Understanding and utilizing these algorithms will greatly aid in achieving good performance in coding tests.<\/p>\n<p>We hope you gain confidence in coding tests by mastering these algorithms through various problems!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello! Today, we will discuss a string search problem to prepare for coding tests. String search problems are fundamentally algorithmic challenges that involve finding specific patterns or substrings within a string. It is important to test efficiency, accuracy, and various methodologies to enhance understanding of how to approach coding test scenarios. Problem Description You are &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33632\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Python Coding Test Course, String Search&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[145],"tags":[],"class_list":["post-33632","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33632\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! Today, we will discuss a string search problem to prepare for coding tests. String search problems are fundamentally algorithmic challenges that involve finding specific patterns or substrings within a string. It is important to test efficiency, accuracy, and various methodologies to enhance understanding of how to approach coding test scenarios. Problem Description You are &hellip; \ub354 \ubcf4\uae30 &quot;Python Coding Test Course, String Search&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33632\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:18:46+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:47:20+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Python Coding Test Course, String Search\",\"datePublished\":\"2024-11-01T09:18:46+00:00\",\"dateModified\":\"2024-11-01T11:47:20+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/\"},\"wordCount\":498,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33632\/\",\"name\":\"Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:18:46+00:00\",\"dateModified\":\"2024-11-01T11:47:20+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33632\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33632\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Python Coding Test Course, String Search\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33632\/","og_locale":"ko_KR","og_type":"article","og_title":"Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! Today, we will discuss a string search problem to prepare for coding tests. String search problems are fundamentally algorithmic challenges that involve finding specific patterns or substrings within a string. It is important to test efficiency, accuracy, and various methodologies to enhance understanding of how to approach coding test scenarios. Problem Description You are &hellip; \ub354 \ubcf4\uae30 \"Python Coding Test Course, String Search\"","og_url":"https:\/\/atmokpo.com\/w\/33632\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:18:46+00:00","article_modified_time":"2024-11-01T11:47:20+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33632\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33632\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Python Coding Test Course, String Search","datePublished":"2024-11-01T09:18:46+00:00","dateModified":"2024-11-01T11:47:20+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33632\/"},"wordCount":498,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33632\/","url":"https:\/\/atmokpo.com\/w\/33632\/","name":"Python Coding Test Course, String Search - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:18:46+00:00","dateModified":"2024-11-01T11:47:20+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33632\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33632\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33632\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Python Coding Test Course, String Search"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33632","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33632"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33632\/revisions"}],"predecessor-version":[{"id":33633,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33632\/revisions\/33633"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}