Algo Advance

Depth-first-search - medium level - question 2 2115. Find All Possible Recipes from Given Supplies You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes. You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them. Return a list of all the recipes that you can create. You may return the answer in any order. Note that two recipes may contain each other in their ingredients. Constraints: n == recipes.length == ingredients.length 1 <= n <= 100 1 <= ingredients[i].length, supplies.length <= 100 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10 recipes[i

1316. Distinct Echo Substrings Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string). Constraints: 1 <= text.length <= 2000 text has only lowercase English letters. Analysis: There are O(N^2) substring in total, and if we check each substring one by one, the time complexity for checking is O(N). So the overall time complexity is O(N^3). The longest test case may have N as 2000, so N^3 ~ 10^10, which is too large. We need to find some other ways faster. One way is to use a rolling hashing method. For a fixed length, we just scan the string from left to right once with double pointers. The first pointer is the ending of the first half; the second one is the ending of the second half. If they are the same, or give the same hash value, then we consider they are the same. To avoid repeating counting, we can use a set. See the code below, class Solution { pu

2156. Find Substring With Given Hash Value The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function: hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m. Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26. You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue. The test cases will be generated such that an answer always exists. A substring is a contiguous non-empty sequence of characters within a string. Constraints: 1 <= k <= s.length <= 2 * 104 1 <= power, modulo <= 109 0 <= hashValue < modulo s consists of lowercase English letters only. The test cases are generated such that an answer always exists. Analysis This is question is about rolling hash. The formula is given, but we cannot use it directly. Or

Rolling Hash - Question List Question 1.  2156. Find Substring With Given Hash Value Question 2.  1316. Distinct Echo Substrings Upper Layer

Rolling hash is one common trick used to increase efficiency of substring comparisons by compressing (or hashing) a string into a integer. After this step, we can compare two strings directly without comparing each chars. So the efficiency can be increased from O(N) to O(1). So how to implement the rolling hash? First we need to choose a base for the expansion and a modulo to mod. The basic formula is (suppose the window is n, and the rolling direction is from left to right), HashVal = (A1*p^(n-1) + A2*p^(n-2) + ... + An-1*p^1 + An*p^0)%mod where HashVal is the hash value, Ai is the ith element, p is the base, and mod is the modulo. To avoid collision as much as we can, p and modulo usually need to be large prime numbers. One corner case is that the base order in the above formula cannot be reversed. Or to be more clear, if the rolling direction is from left to right in an array, the first element should be in the highest order of the base, or times p^(n-1), and the last element times