# Save Humanity – HackerRank Solution

In this post, we will solve Save Humanity HackerRank Solution. This problem (Save Humanity) is a part of HackerRank Problem Solving series.

Contents

## Solution – Save Humanity – HackerRank Solution

### Python

```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))
```

### 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 {

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

private static List<Integer> z_function(String s) {
List<Integer> z = new ArrayList(s.length());
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;
}
}
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];