{"id":9487,"date":"2022-02-05T18:19:25","date_gmt":"2022-02-06T02:19:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9487"},"modified":"2022-02-05T18:21:19","modified_gmt":"2022-02-06T02:21:19","slug":"leetcode-2156-find-substring-with-given-hash-value","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-2156-find-substring-with-given-hash-value\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2156. Find Substring With Given Hash Value"},"content":{"rendered":"\n<p>The hash of a&nbsp;<strong>0-indexed<\/strong>&nbsp;string&nbsp;<code>s<\/code>&nbsp;of length&nbsp;<code>k<\/code>, given integers&nbsp;<code>p<\/code>&nbsp;and&nbsp;<code>m<\/code>, is computed using the following function:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>hash(s, p, m) = (val(s[0]) * p<sup>0<\/sup>&nbsp;+ val(s[1]) * p<sup>1<\/sup>&nbsp;+ ... + val(s[k-1]) * p<sup>k-1<\/sup>) mod m<\/code>.<\/li><\/ul>\n\n\n\n<p>Where&nbsp;<code>val(s[i])<\/code>&nbsp;represents the index of&nbsp;<code>s[i]<\/code>&nbsp;in the alphabet from&nbsp;<code>val('a') = 1<\/code>&nbsp;to&nbsp;<code>val('z') = 26<\/code>.<\/p>\n\n\n\n<p>You are given a string&nbsp;<code>s<\/code>&nbsp;and the integers&nbsp;<code>power<\/code>,&nbsp;<code>modulo<\/code>,&nbsp;<code>k<\/code>, and&nbsp;<code>hashValue.<\/code>&nbsp;Return&nbsp;<code>sub<\/code>,<em>&nbsp;the&nbsp;<strong>first<\/strong>&nbsp;<strong>substring<\/strong>&nbsp;of&nbsp;<\/em><code>s<\/code><em>&nbsp;of length&nbsp;<\/em><code>k<\/code><em>&nbsp;such that&nbsp;<\/em><code>hash(sub, power, modulo) == hashValue<\/code>.<\/p>\n\n\n\n<p>The test cases will be generated such that an answer always&nbsp;<strong>exists<\/strong>.<\/p>\n\n\n\n<p>A&nbsp;<strong>substring<\/strong>&nbsp;is a contiguous non-empty sequence of characters within a string.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"leetcode\", power = 7, modulo = 20, k = 2, hashValue = 0\n<strong>Output:<\/strong> \"ee\"\n<strong>Explanation:<\/strong> The hash of \"ee\" can be computed to be hash(\"ee\", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0. \n\"ee\" is the first substring of length 2 with hashValue 0. Hence, we return \"ee\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"fbxzaad\", power = 31, modulo = 100, k = 3, hashValue = 32\n<strong>Output:<\/strong> \"fbx\"\n<strong>Explanation:<\/strong> The hash of \"fbx\" can be computed to be hash(\"fbx\", 31, 100) = (6 * 1 + 2 * 31 + 24 * 31<sup>2<\/sup>) mod 100 = 23132 mod 100 = 32. \nThe hash of \"bxz\" can be computed to be hash(\"bxz\", 31, 100) = (2 * 1 + 24 * 31 + 26 * 31<sup>2<\/sup>) mod 100 = 25732 mod 100 = 32. \n\"fbx\" is the first substring of length 3 with hashValue 32. Hence, we return \"fbx\".\nNote that \"bxz\" also has a hash of 32 but it appears later than \"fbx\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= k &lt;= s.length &lt;= 2 * 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= power, modulo &lt;= 10<sup>9<\/sup><\/code><\/li><li><code>0 &lt;= hashValue &lt; modulo<\/code><\/li><li><code>s<\/code>&nbsp;consists of lowercase English letters only.<\/li><li>The test cases are generated such that an answer always&nbsp;<strong>exists<\/strong>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sliding window<\/strong><\/h2>\n\n\n\n<p>hash = (((<meta charset=\"utf-8\">hash &#8211; (s[i+k] * p<sup>k-1<\/sup>) % mod + mod) * p) + (s[i] * p<sup>0<\/sup>)) % mod<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  string subStrHash(string s, int power, int modulo, int k, int hashValue) {    \n    const int n = s.length();\n    long p = 1; \n    for (int i = 1; i < k; ++i)\n      p = (p * power) % modulo;\n    long ans = 0;\n    for (long i = n - 1, cur = 0; i >= 0; --i) {\n      if (i + k < n) \n        cur = ((cur - (s[i + k] - 'a' + 1) * p) % modulo + modulo) % modulo;\n      cur = (cur * power + (s[i] - 'a' + 1)) % modulo;      \n      if (i + k <= n &#038;&#038; cur == hashValue) \n        ans = i;\n    }    \n    return s.substr(ans, k);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>The hash of a&nbsp;0-indexed&nbsp;string&nbsp;s&nbsp;of length&nbsp;k, given integers&nbsp;p&nbsp;and&nbsp;m, is computed using the following function: hash(s, p, m) = (val(s[0]) * p0&nbsp;+ val(s[1]) * p1&nbsp;+ &#8230; +&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[177,571,215,4],"class_list":["post-9487","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-medium","tag-rolling-hash","tag-sliding-window","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9487","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9487"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9487\/revisions"}],"predecessor-version":[{"id":9490,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9487\/revisions\/9490"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9487"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9487"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9487"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}