HackerRank Save Humanity Problem Solution Yashwant Parihar, May 2, 2023March 27, 2024 In this post, we will solve HackerRank Save Humanity Problem Solution. Oh!! Mankind is in trouble again. This time, it’s a deadly disease spreading at a rate never seen before. The need of the hour is to set up efficient virus detectors. You are the lead at Central Hospital and you need to find a fast and reliable way to detect the footprints of the virus DNA in that of the patient. The DNA of the patient as well as of the virus consists of lowercase letters. Since the collected data is raw, there may be some errors. You will need to find all substrings in the patient DNA that either exactly match the virus DNA or have at most one mismatch, i.e., a difference in at most one location. For example, “aa” and “aa” are matching, “ab” and “aa” are matching, while “abb” and “bab” are not. Function Description Complete the virusIndices function in the editor below. It should print a list of space-separated integers that represent the starting indices of matching substrings in increasing order, or No match!. virusIndices has the following parameter(s): p: a string that represents patient DNA v: a string that represents virus DNA Input Format The first line contains an integer t, the number of test cases.. Each of the next lines contains two space-separated strings p (the patient DNA) and v (the virus DNA). Output FormatFor each test case, output a single line containing a space-delimited list of starting indices (0 -indexed) of substrings of p which are matching with v according to the condition mentioned above. The indices have to be in increasing order. If there is no matching substring, output No Match!. Sample Input 0 3 abbab ba hello world banana nan Sample Output 0 1 2 No Match! 0 2 Explanation 0For the first case, the substrings of p starting at indices 1 and 2 are “bb” and “ba” and they are matching with the string which is “ba”.For the second case, there are no matching substrings so the output is No Match!.For the third case, the substrings of p starting at indices 0 and 2 are “ban” and “nan” and they are matching with the string which is “nan”. Sample Input 1 3 cgatcg gc atcgatcga cgg aardvark ab Sample Output 1 1 3 2 6 0 1 5 Explanation 1For the first case, the substrings of p starting at indices 1 and 3 are “ga” and “gc” and theyare matching with the string which is “gc”.For the second case, the substrings of p starting at indices 2 and 6 are “cga” and “cga” and they are matching with the string which is “cgg”.For the third case, the substrings of p starting at indices 0, 1 and 5 are “aa”, “ar” and “ar” and they are matching with the string which is “ab”. HackerRank Save Humanity Problem Solution Save Humanity C++ Solution #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> Z(string s) { vector<int> z = {0}; int l = 0, r = 0; for (int i = 1; i < s.size(); i++) { if (i >= r) { r = l = i; while (r < s.size() && s[r-i] == s[r]) r++; z.push_back(r-i); } else { if (z[i-l] < r-i) { z.push_back(z[i-l]); } else { l = i; while (r < s.size() && s[r-i] == s[r]) r++; z.push_back(r-i); } } } return z; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { string text, pat; cin >> text >> pat; auto a = Z(pat+"@"+text); reverse(text.begin(),text.end()); reverse(pat.begin(),pat.end()); auto b = Z(pat+"@"+text); vector<int> ans; for (int i = 0; i+pat.size() <= text.size(); i++) { if (a[pat.size()+1+i]+b[pat.size()+1+text.size()-(i+pat.size())]+1 >= pat.size()) ans.push_back(i); } if (ans.empty()) cout << "No Match!" << endl; else { for (int i : ans) cout << i << ' '; cout << endl; } } } Save Humanity C Sharp Solution using System.CodeDom.Compiler; using System.Collections.Generic; using System.Collections; using System.ComponentModel; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.IO; using System.Linq; using System.Reflection; using System.Runtime.Serialization; using System.Text.RegularExpressions; using System.Text; using System; class Result { static int [] Zvalue(string s) { int[] z = new int[s.Length]; int n = s.Length; int L = 0, R = 0; for (int i = 1; i < n; i++) { if (i > R) { L = R = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } else { int k = i - L; if (z[k] < R - i + 1) z[i] = z[k]; else { L = i; while (R < n && s[R - L] == s[R]) R++; z[i] = R - L; R--; } } } return z; } public static void virusIndices(string P, string V) { string S1 = V + "#" + P; string rV = new string(V.Reverse ().ToArray ()); string rP = new string(P.Reverse().ToArray()); string S2 = rV + "#" + rP; int[] Z1 = Zvalue (S1); int[] Z2 = Zvalue (S2); int N = V.Length; int M = P.Length; int L = S1.Length; List<int> results = new List<int> (); for (int i = 0; i <= M - N; i++) { if (Z1[N+1+i] == N) results.Add (i); else { int m1 = Z1[N + 1 + i]; int m2 = Z2[L - (i + N)]; //if (i == 0) // Console.WriteLine("{0}+{1}", m1, m2); if (m1 + m2 + 1 >= N) results.Add (i); } } Console.WriteLine (results.Count()>0 ?string.Join (" ", results.Select (x => x.ToString ()).ToArray ()):"No Match!"); } } class Solution { public static void Main(string[] args) { int t = Convert.ToInt32(Console.ReadLine().Trim()); for (int tItr = 0; tItr < t; tItr++) { string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' '); string p = firstMultipleInput[0]; string v = firstMultipleInput[1]; Result.virusIndices(p, v); } } } Save Humanity Java Solution import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; import java.util.stream.Collectors; public class Solution { /* * Complete the virusIndices function below. */ static List<Integer> virusIndices(String p, String v) { List<Integer> z = z_function(v + "#" + p); List<Integer> z_reversed = z_function(new StringBuilder(v).reverse().toString() + "#" + new StringBuilder(p).reverse().toString()); List<Integer> answer = new ArrayList<>(); for (int i = 0; i <= p.length() - v.length(); ++i) { if (z.get(i + v.length() + 1) + z_reversed.get(p.length() - i + 1) >= v.length() - 1) { answer.add(i); } } return answer; } private static List<Integer> z_function(String s) { List<Integer> z = new ArrayList(s.length()); z.add(0); int l = 0; int r = 0; for (int i = 1; i < s.length(); ++i) { int z_i = 0; if (i <= r) z_i = r - i + 1 < z.get(i - l) ? r - i + 1 : z.get(i - l); while (i + z_i < s.length() && s.charAt(z_i) == s.charAt(i + z_i)) ++z_i; if (i + z_i - 1 > r) { l = i; r = i + z_i - 1; } z.add(z_i); } return z; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int t = Integer.parseInt(scanner.nextLine().trim()); for (int tItr = 0; tItr < t; tItr++) { String[] pv = scanner.nextLine().split(" "); String p = pv[0]; String v = pv[1]; List<Integer> answer = virusIndices(p, v); if (answer.size() == 0) { System.out.println("No Match!"); } else { System.out.println(answer.stream().map(String::valueOf).collect(Collectors.joining(" "))); } } } } Save Humanity JavaScript Solution 'use strict'; process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', inputStdin => { inputString += inputStdin; }); process.stdin.on('end', _ => { inputString = inputString.trim().split('\n').map(str => str.trim()); main(); }); function readLine() { return inputString[currentLine++]; } /* * Complete the virusIndices function below. */ function stringDiffThreshold(s1, s2, max = 0, score = 0) { var len = s1.length; if (s1 !== s2 && len > 1) { var len2 = Math.ceil(len / 2); score = stringDiffThreshold(s1.substr(0, len2), s2.substr(0, len2), max, score); if (score > max) return score; score = stringDiffThreshold(s1.substr(len2), s2.substr(len2), max, score); if (score > max) return score; } else if (s1 !== s2 && len === 1) { //console.log(len + '/:' + s1 + '!==' + s2); return score + 1; } else { //console.log(len + '/:' + s1 + '===' + s2); } return score; } function virusIndices(p, v) { var out = []; for (var i = 0; i < p.length - v.length+1; i++) { if (stringDiffThreshold(p.substr(i, v.length), v, 1) < 2) out.push(i); } if (out.length > 0) console.log(out.join(' ')); else console.log('No Match!'); } function main() { const t = parseInt(readLine(), 10); for (let tItr = 0; tItr < t; tItr++) { const pv = readLine().split(' '); const p = pv[0]; const v = pv[1]; virusIndices(p, v); } } Save Humanity Python Solution #!/bin/python3 import os import sys # # Complete the virusIndices function below. # def binSearch(smaller, bigger): lo = 0 hi = len(smaller) # binary search for prefix while lo < hi: # +1 for even lengths mid = ((hi - lo + 1) // 2) + lo if smaller[:mid] == bigger[:mid]: # prefixes equal lo = mid else: # prefixes not equal hi = mid - 1 return lo def virusIndices(p, v): # # Print the answer for this test case in a single line # ''' This is about pattern searching, an important problem in computer science. ''' txt = p pat = v N = len(txt) M = len(pat) err_allowance = 1 matches=[] debug = False if debug: print(f"N {N} M {M}") txt_run_starts = [] #int run_start txt_run_ch = [] #str ch ''' txt_run_matches_pat = [] #bool matches_pat ch_pat_match = {} # str ch : bool matches_pat for i in range(26): ch = chr(ord("a") + i) ch_pat_match[ch] = pat.count(ch) >= M-err_allowance ''' i = 0 while i < N: ch = txt[i] streak_start = i i += 1 while i < N and txt[i] == ch: i += 1 txt_run_starts.append(streak_start) txt_run_ch.append(ch) #txt_run_matches_pat.append(ch_pat_match[ch]) txt_run_starts.append(N) if debug: print(f"len(txt_run_starts) {len(txt_run_starts)} N {N}") txt_run_lens = [txt_run_starts[i]-txt_run_starts[i-1] for i in range(1,len(txt_run_starts))] if debug: print(f"max txt_run_lens {max(txt_run_lens)}") ##print(f"txt_run_starts\n{txt_run_starts}") pat_run_starts = [] #int pat_run_ch = [] #str ch j = 0 while j < M: ch = pat[j] streak_start = j j += 1 while j < M and pat[j] == ch: j += 1 pat_run_starts.append(streak_start) pat_run_ch.append(ch) pat_run_starts.append(M) if debug: print(f"len(pat_run_starts) {len(pat_run_starts)} M {M}") pat_run_lens = [pat_run_starts[i]-pat_run_starts[i-1] for i in range(1,len(pat_run_starts))] if debug: print(f"max pat_run_lens {max(pat_run_lens)}") ##print(f"pat_run_starts\n{pat_run_starts}") # KMP preprocessing: lps = [0]*M disable_KMP = True #LPS example: ABXAB gives lps of [0 0 0 1 2] #Search examples using this pattern with error_allowance == 1 #txt: ABXABXABX #pat: ABXAB #matches: # match found at i-j=0 with 0 errors with j=0..5, lps[j-1]=2 # match found at i-j=3 with 0 errors with j=2..5, lps[j-1]=2 # match found at i-j=5 with 0 errors with j=2..5, lps[j-1]=2 # exit on i-j=5 which has reached N-M+1=9-5+1=5 #txt: ABCABCDBXAB #pat: ABXAB # matches found at 0, 3, 6 if disable_KMP: pass elif max(pat_run_lens) < M ** 0.5: # pat runs aren't very long - use standard preprocessing for KMP for j in range(M): k = 0 while k < j: if pat[:k+1] != pat[j-k:j+1]: break k += 1 lps[j] = k else: # pat runs are sizable - use skip-ahead preprocessing for KMP suffix_run_at_k_eq_0 = 0 for j in range(M): if debug and j%5000==0: print(f"j {j}") # check for degenerate case of all one character if 0 < j < pat_run_lens[0]: lps[j] = j continue if j >= pat_run_starts[suffix_run_at_k_eq_0 + 1]: suffix_run_at_k_eq_0 += 1 # check for degenerate case where j has 2 bracketing runs of unequal length and identical character if j > pat_run_lens[0]: len_first_prefix_run = pat_run_lens[0] len_last_suffix_run = j+1 - pat_run_starts[suffix_run_at_k_eq_0] if len_first_prefix_run != len_last_suffix_run and pat_run_ch[0] == pat_run_ch[suffix_run_at_k_eq_0]: lps[j] = min(len_first_prefix_run, len_last_suffix_run) continue # handle more general case of matching lists of prefix and suffix runs prefix_runs = [0] suffix_runs = [suffix_run_at_k_eq_0] # uses reverse order k = 0 while k < j: #if pat[:k+1] != pat[j-k:j+1]: # break if len(prefix_runs) != len(suffix_runs): # mismatch in number of runs in comparators break len_last_prefix_run = k+1 - pat_run_starts[prefix_runs[-1]] len_last_suffix_run = j+1 - max(j-k, pat_run_starts[suffix_runs[0]]) if len_last_prefix_run != len_last_suffix_run or pat_run_ch[prefix_runs[-1]] != pat_run_ch[suffix_runs[0]]: # special case comparison for tail stub of prefix and tail stub of suffix break if len(prefix_runs)>1: len_first_prefix_run = min(k+1, pat_run_lens[prefix_runs[0]]) len_first_suffix_run = min(j+1, pat_run_starts[suffix_runs[-1] + 1]) - (j-k) if len_first_prefix_run != len_first_suffix_run or pat_run_ch[prefix_runs[0]] != pat_run_ch[suffix_runs[-1]]: # special case comparison for head of prefix (not nec. a stub) head stub of suffix break for i in range(1, len(prefix_runs) - 1): # compare all intermediate runs of prefix and suffix (length and run character) if pat_run_lens[prefix_runs[i]] != pat_run_lens[suffix_runs[-i-1]] or pat_run_ch[prefix_runs[i]] != pat_run_ch[suffix_runs[-i-1]]: break k += 1 if k >= pat_run_starts[prefix_runs[-1] + 1]: prefix_runs.append(prefix_runs[-1] + 1) if j-k < pat_run_starts[suffix_runs[-1]]: suffix_runs.append(suffix_runs[-1] - 1) lps[j] = k debuggy = 0 #if False: # DEBUG - force skip-ahead branch if max(txt_run_lens) < N ** 0.5 and max(pat_run_lens) < M ** 0.5: #runs aren't very long - try naive approach or KMP # KMP pattern search with error allowance: i, j = 0, 0 err_count = 0 if disable_KMP: use_block_compare = True if not use_block_compare: # naive algorithm while i-j <= N-M: got_match = txt[i]==pat[j] if got_match or err_count < err_allowance: i, j = i+1, j+1 if j==M: matches.append(i-j) i, j = i-j+1, 0 err_count=0 elif not got_match: err_count+=1 else: i, j = i-j+1, 0 err_count=0 else: # naive algorithm, but using block compare of strings block_size = 64 while i-j <= N-M: while i+block_size<=N and j+block_size<=M and txt[i:i+block_size]==pat[j:j+block_size]: i += block_size j += block_size if j==M: matches.append(i-j) i, j = i-j+1, 0 err_count=0 i_start = i while (i==i_start or i % block_size != 0) and i-j <= N-M: got_match = txt[i]==pat[j] if got_match or err_count < err_allowance: i, j = i+1, j+1 if j==M: matches.append(i-j) i, j = i-j+1, 0 err_count=0 elif not got_match: err_count+=1 else: i, j = i-j+1, 0 err_count=0 else: ''' # KMP algorithm - no error allowance while i-j <= N-M: if txt[i]==pat[j]: i, j = i+1, j+1 if j==M: matches.append[i-j] j=lps[j-1] elif j==0: i = i+1 else: j=lps[j-1] ''' # KMP algorithm while i-j <= N-M: got_match = txt[i]==pat[j] if got_match or err_count < err_allowance: i, j = i+1, j+1 if not got_match: err_count+=1 if j==M: matches.append(i-j) if err_count > 0 or disable_KMP: i = i-j + 1 j = 0 err_count = 0 else: j=lps[j-1] else: i = i-j + 1 j = 0 err_count = 0 else: #there are some runs of significant length - try optimizing for this # KMP algorithm with err_allowance and skip-ahead logic i, j = 0, 0 err_count = 0 i_txt_run, j_pat_run = 0, 0 while i-j <= N-M: while True: txt_run_len = txt_run_starts[i_txt_run + 1] - i pat_run_len = pat_run_starts[j_pat_run + 1] - j if txt_run_ch[i_txt_run] != pat_run_ch[j_pat_run]: break max_run_len = min(txt_run_len, pat_run_len) skip_len = min(M-j, max_run_len) i, j = i+skip_len, j+skip_len if txt_run_len == skip_len: i_txt_run += 1 if pat_run_len == skip_len: j_pat_run += 1 if j==M: matches.append(i-j) if err_count > 0 or disable_KMP: i = i-j + 1 j = 0 err_count = 0 while i < txt_run_starts[i_txt_run]: i_txt_run -= 1 j_pat_run = 0 else: j=lps[j-1] while j < pat_run_starts[j_pat_run]: j_pat_run -= 1 if i-j>N-M: break if i-j>N-M: break # we have a mismatch if err_count < err_allowance: i, j = i+1, j+1 err_count+=1 if i>= txt_run_starts[i_txt_run + 1]: i_txt_run += 1 if j==M: matches.append(i-j) if err_count > 0 or disable_KMP: i = i-j + 1 j = 0 err_count = 0 while i < txt_run_starts[i_txt_run]: i_txt_run -= 1 j_pat_run = 0 else: j=lps[j-1] while j < pat_run_starts[j_pat_run]: j_pat_run -= 1 else: if j>= pat_run_starts[j_pat_run + 1]: j_pat_run += 1 else: i = i-j + 1 j = 0 err_count = 0 while i < txt_run_starts[i_txt_run]: i_txt_run -= 1 j_pat_run = 0 print(*matches) if len(matches)>0 else print("No Match!") if __name__ == '__main__': global count_of_target_M_cases count_of_target_M_cases = 0 sys_stdin_orig = sys.stdin if len(sys.argv) > 1 and sys.argv[1]=="<": sys.stdin = open(sys.argv[2], "r") t = int(input()) for t_itr in range(t): pv = input().split() p = pv[0] v = pv[1] virusIndices(p, v) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython