In this HackerRank Save Humanity problem solution, we have given 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.
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))
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;
}
