HackerRank Save Humanity problem solution

In this 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 t lines contains two space-separated strings p (the patient DNA) and v (the virus DNA).

HackerRank Save Humanity problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'virusIndices' function below.
#
# The function accepts following parameters:
#  1. STRING p
#  2. STRING v
#
def small_match(w1, w2):
    counter = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            counter += 1
            if counter > 1:
                return 0
    return 1


def match(w1, w2):
    length = len(w1)
    if length < 10:
        return small_match(w1, w2)
    w11 = w1[:length // 2]
    w12 = w1[length // 2:]
    w21 = w2[:length // 2]
    w22 = w2[length // 2:]

    s1 = (w11 == w21)
    s2 = (w12 == w22)

    if s1 and s2:
        return True
    elif s1 and not s2:
        return match(w12, w22)
    elif not s1 and s2:
        return match(w11, w21)
    else:
        return False


def virusIndices(p, v):

    res = ''
    if len(v) > len(p):
        return "No Match!"
    else:
        for i in range(len(p) - len(v) + 1):
            temp = p[i:i + len(v)]

            flag = match(temp, v)
            if flag:
                res += str(i) + ' '
        if len(res) == 0:
            return "No Match!"
        else:
            return res.strip()

if __name__ == '__main__':
    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        p = first_multiple_input[0]

        v = first_multiple_input[1]

        print(virusIndices(p, v))

Save Humanity problem solution in Java.

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(" ")));
            }
        }
    }
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 200005;

void e_kmp(char *s, char *t, int *has, int *e_has)
{
	int sp, p, mx, tn;
	for (sp = p = mx = 0; s[p] > 0; p++)
	{
		if (mx == p || p + e_has[p - sp] >= mx)
		{
			for (tn = mx - p; s[mx] == t[tn]; tn++)
				mx++;
			has[sp = p] = mx - p;
			if (mx == p)
				sp = mx = p + 1;
		}
		else
			has[p] = e_has[p - sp];
	}
}
char s[MaxN],t[MaxN];
int A[MaxN],B[MaxN],A2[MaxN],B2[MaxN];
int ans[MaxN],n,m;

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%s%s",s,t);
		n = strlen(s), m = strlen(t);
		t[m] = -1;
		A[0] = m;
		e_kmp(t+1,t,A+1,A);
		e_kmp(s,t,B,A);
		reverse(s,s+n);
		reverse(t,t+m);
		A2[0] = m;
		e_kmp(t+1,t,A2+1,A2);
		e_kmp(s,t,B2,A2);

		int cnt = 0;
		for(int i = 0; i+m-1 < n; i++)
		{
			if(B[i]>=m || B2[n-(i+m)]+B[i]>=m-1)
				ans[cnt++] = i;
		}
		for(int i = 0; i < cnt; i++)
			printf("%d%c",ans[i],i==cnt-1?'n':' ');
		if(cnt==0)puts("");
	}

	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define kMaxSize 100001
#define kMaxMismatch 1

typedef long long int lli;

int findDna8b(char* p, char* v, int vc);

int main()
{
    // Allocate memory for strings.
    char* p = (char*)malloc(kMaxSize * sizeof(char));
    char* v = (char*)malloc(kMaxSize * sizeof(char));
    
    // Test cases.
    int tc;
    scanf("%d", &tc);
    while (0 < tc--)
    {
        // Load strings.
        scanf("%s %s", p, v);
        int pc = (int)strlen(p);
        int vc = (int)strlen(v);
        
        // Look for v in p. Print starting index of each match.
        int c = (pc-vc);
        int matched = 0;
        for (int i = 0; i <= c; i++){
            if (findDna8b(&p[i], v, vc) == 1){
                matched++;
                printf("%d ", i);
            }
        }
        
        // We have to indicate if no matches were found.
        if (matched <= 0)
            printf("No Match!n");
        else
            printf("n");
    }
    
    return 0;
}

int findDna8b(char* p, char* v, int vc)
{
    lli* p8 = (lli*)p;
    lli* v8 = (lli*)v;
    
    int c = vc/8;
    int mismatch = 0;
    int i;
    for (i = 0; i < c; i++){
        if (p8[i] != v8[i])
        {
            for (int j = i*8; j < (i*8)+8; j++){
                if (p[j] != v[j]){
                    mismatch++;
                    if (mismatch > kMaxMismatch) return -1;
                }
            }
        }
    }
    
    for (int j = i*8; j < vc; j++){
        if (p[j] != v[j]){
            mismatch++;
            if (mismatch > kMaxMismatch) return -1;
        }
    }
    
    return 1;
}