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.

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

Note: This problem (Save Humanity) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.