Save Humanity – HackerRank
Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<stdlib.h>
using namespace std ;
#define MAXN 200002
char text[MAXN],pat[MAXN] ;
int szp,szt ;
int p1[2 * MAXN],p2[2 * MAXN] ;
char s[2 * MAXN] ;
vector<int> reta ;
vector<int> solve1()
{
memset(p1,0,sizeof p1) ;
memset(p2,0,sizeof p2) ;
memset(s,0,sizeof s) ;
int n = 0 ;
for(int i = 0;i < szp;i++) s[n++] = pat[i] ;
for(int i = 0;i < szt;i++) s[n++] = text[i] ;
p1[0] = n ;
int g = 0,f = 0 ;
for(int i = 1;i < n;i++)
{
if(i < g && p1[i - f] != g - i)
p1[i] = min(p1[i - f],g - i) ;
else
{
g = max(g,i) ;
f = i ;
while(g < n && s[g] == s[g - f]) g++ ;
p1[i] = g - f ;
}
}
n = 0 ;
for(int i = szp - 1;i >= 0;i--) s[n++] = pat[i] ;
for(int i = szt - 1;i >= 0;i--) s[n++] = text[i] ;
p2[0] = n ;
g = 0,f = 0 ;
for(int i = 1;i < n;i++)
{
if(i < g && p2[i - f] != g - i)
p2[i] = min(p2[i - f],g - i) ;
else
{
g = max(g,i) ;
f = i ;
while(g < n && s[g] == s[g - f]) g++ ;
p2[i] = g - f ;
}
}
reta.clear() ;
for(int i = 0;i + szp <= szt;i++)
{
int start = p1[szp + i] ;
int end = p2[szp + szt - 1 - (i + szp - 1)] ;
if(start + end + 1 >= szp) reta.push_back(i) ;
}
return reta ;
}
vector<int> solve2()
{
vector<int> ret ;
for(int i = 0;i + szp <= szt;i++)
{
int miss = 0 ;
for(int j = 0;j < szp;j++)
if(text[i + j] != pat[j])
miss++ ;
if(miss <= 1) ret.push_back(i) ;
}
return ret ;
}
void gen()
{
szt = rand() % 1000 + 1 ;
memset(text,0,sizeof text) ;
for(int i = 0;i < szt;i++) text[i] = rand() % 3 + 'a' ;
szp = rand() % szt + 1 ;
memset(pat,0,sizeof pat) ;
for(int i = 0;i < szp;i++) pat[i] = rand() % 3 + 'a' ;
}
char get1()
{
if(rand() % 50000 < 49998) return 'a' ;
else if(rand() % 100 < 80) return 'b' ;
return 'c' ;
}
char get2()
{
if(rand() % 50000 < 49999) return 'a' ;
return 'b' ;
}
void generate()
{
srand(time(NULL)) ;
char in[10] = "in .txt" ;
for(int test = 0;test < 10;test++)
{
in[2] = test + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 10 ;
fprintf(fout,"%d\n",runs) ;
for(int t = 0;t < runs;t++)
{
szt = 100000 - rand() % 1000 + 1 ;
if(test <= 2) szt = rand() % 30 + 1 ;
szp = rand() % szt + 1 ;
memset(text,0,sizeof text) ;
memset(pat,0,sizeof pat) ;
if(test <= 2)
{
for(int i = 0;i < szt;i++) text[i] = rand() % 2 + 'a' ;
for(int i = 0;i < szp;i++) pat[i] = rand() % 2 + 'a' ;
}
else if(test <= 5)
{
for(int i = 0;i < szt;i++) text[i] = get1() ;
for(int i = 0;i < szp;i++) pat[i] = get1() ;
}
else if(test <= 7)
{
for(int i = 0;i < szt;i++) text[i] = get2() ;
for(int i = 0;i < szp;i++) pat[i] = get2() ;
}
else
{
for(int i = 0;i < szt;i++) text[i] = i % 26 + 'a' ;
for(int i = 0;i < szp;i++) pat[i] = i % 26 + 'a' ;
for(int i = 0;i < 10;i++) text[rand() % szt] = 'a' + rand() % 26 ;
}
fprintf(fout,"%s\n%s\n\n",text,pat) ;
}
}
}
void test()
{
for(int t = 0;t < 1000;t++)
{
gen() ;
vector<int> ret1 = solve1() ;
vector<int> ret2 = solve2() ;
for(int i = 0;i < ret1.size();i++) cout << ret1[i] << " " ; cout << endl ;
for(int i = 0;i < ret2.size();i++) cout << ret2[i] << " " ; cout << endl ;
cout << endl ;
if(ret1 != ret2)
{
cout << "Failed on: " << t << endl ;
cout << text << endl << pat << endl ;
for(int i = 0;i < ret1.size();i++) cout << ret1[i] << " " ; cout << endl ;
for(int i = 0;i < ret2.size();i++) cout << ret2[i] << " " ; cout << endl ;
while(1) ;
}
}
}
int main()
{
// srand(time(NULL));
// generate() ; return 0 ;
// test() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
memset(text,0,sizeof text) ;
memset(pat,0,sizeof pat) ;
scanf("%s%s",text,pat) ;
szt = strlen(text) ;
szp = strlen(pat) ;
vector<int> ret1 = solve1() ;
for(int i = 0;i < ret1.size();i++)
{
if(i > 0) printf(" ") ;
printf("%d",ret1[i]) ;
}
printf("\n") ;
}
return 0 ;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.StringTokenizer;
public class Solution {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
char[] t, p;
private void solve() throws IOException {
// stress();
// timing();
int tc = nextInt();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
t = nextToken().toCharArray();
p = nextToken().toCharArray();
List<Integer> answerFast = solveFast();
print(answerFast);
}
}
Random r = new Random(123456789L);
char[] gen(int len, int letters) {
char[] s = new char[len];
for (int i = 0; i < len; i++) {
s[i] = (char) ('a' + r.nextInt(letters));
}
return s;
}
private void stress() {
int numTc = 1000000;
for (int tc = 0; tc < numTc; tc++) {
System.out.print("Stress " + tc + ":");
int tLen = 1 + r.nextInt(200);
t = gen(tLen, 2);
int pLen = Math.min(tLen, 1 + r.nextInt(4));
p = gen(pLen, 2);
List<Integer> answerFast = solveFast();
List<Integer> answerNaive = solveNaive();
if (!answerFast.equals(answerNaive)) {
throw new IllegalStateException(new String(t) + "/" + new String(p) + ": " + answerFast + " vs. " + answerNaive);
}
System.out.println(" (OK - " + answerFast.size() + " elements)");
}
}
private void timing() {
int numTc = 10;
for (int tc = 0; tc < numTc; tc++) {
System.out.print("Timing " + tc + ":");
int tLen = 100000;
t = gen(tLen, 1);
int pLen = 1;
p = gen(pLen, 1);
List<Integer> answerFast = solveFast();
System.out.println(" (OK - " + answerFast.size() + " elements)");
}
}
private void print(List<Integer> answerNaive) {
boolean first = true;
for (int v : answerNaive) {
if (!first) {
out.print(' ');
}
out.print(v);
first = false;
}
out.println();
}
private List<Integer> solveFast() {
char[] pt = concat(p, t);
int[] z = calcZ(pt);
char[] ptRev = concatRev(p, t);
int[] zRev = calcZ(ptRev);
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i <= t.length - p.length; i++) {
int commonPrefix = z[p.length + i + 1];
boolean match = false;
if (commonPrefix >= p.length) {
// entire match is found
match = true;
} else if (commonPrefix == p.length - 1) {
// last character is different, but it's okay
match = true;
} else {
// check remaining characters in a reversed string
int len = p.length - commonPrefix - 1;
// index in the original string
int nI = i + p.length - 1;
// index in the reversed string
nI = t.length - nI - 1;
// index in the concatenated reversed string
nI += p.length + 1;
// check the number of matching characters in a reverse string
if (zRev[nI] >= len) {
match = true;
}
}
if (match) {
result.add(i);
}
}
return result;
}
private char[] concat(char[] p, char[] t) {
char[] result;
StringBuilder ptBuf = new StringBuilder();
ptBuf.append(p);
ptBuf.append('#');
ptBuf.append(t);
result = ptBuf.toString().toCharArray();
return result;
}
private char[] concatRev(char[] p, char[] t) {
char[] result;
StringBuilder ptBuf = new StringBuilder();
ptBuf.append(t);
ptBuf.append('#');
ptBuf.append(p);
result = ptBuf.reverse().toString().toCharArray();
return result;
}
private int[] calcZ(char[] s) {
int[] z = new int[s.length];
for (int i = 1, l = 0, r = 0; i < s.length; ++i) {
if (i <= r) {
z[i] = Math.min(r - i + 1, z[i - l]);
}
while (i + z[i] < s.length && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
private List<Integer> solveNaive() {
List<Integer> result = new ArrayList<Integer>();
for (int i = 0; i <= t.length - p.length; i++) {
int mismatches = 0;
for (int j = 0; j < p.length; j++)
if (t[i + j] != p[j]) {
mismatches++;
if (mismatches > 1) {
break;
}
}
if (mismatches <= 1) {
result.add(i);
}
}
return result;
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new BufferedWriter(new FileWriter(FILE_OUT)));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
}
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
def compare(word1, word2):
one_wrong = False
for i in range(len(word1)):
if word1[i] != word2[i]:
if one_wrong:
return False
one_wrong = True
return True
def compare_first(word1, word2):
l = len(word1)
if l<10:
return compare(word1, word2)
first_half = (word1[:l/2] == word2[:l/2])
second_half = (word1[l/2:] == word2[l/2:])
if first_half:
if second_half:
return True
else:
return compare_first(word1[l/2:], word2[l/2:])
else:
if not(second_half):
return False
else:
return compare_first(word1[:l/2], word2[:l/2])
def matchestowithinone(dna, virus):
return_string = ""
virlen = len(virus)
for i in range(len(dna)-virlen+1):
dnaword = dna[i:i+virlen]
matches = compare_first(dnaword, virus)
if matches:
return_string+=str(i)
return_string+=" "
return return_string
input = sys.stdin
case_count = int(input.readline())
for i in range(case_count):
dna = input.readline().strip()
virus = input.readline().strip()
blank = input.readline()
result = matchestowithinone(dna, virus).strip()
print result
Python 3 rep HackerRank Solution
def similarity(st):
rt = [len(st)]
i = 1;f,fi = 0,0
k = 0
while i < len(st):
if fi < i < (fi+f):
if rt[i-fi] >= fi+f-i:
k = fi+f-i
f,fi = 0,0
else:
rt.append(rt[i-fi])
i+=1
k = 0
else:
while i+k < len(st) and st[k] == st[i+k]: k+=1
rt.append(k)
f,fi = k,i
i+=1
k = 0
return (rt)
def similarityDiff(st,t):
tmp = similarity(t)
i = 0
rt = []
j = 0
while i < len(st):
while i+j < len(st) and j < len(t):
if st[i+j] != t[j]: rt.append(j);break
j+=1
else:
rt.append(j)
if rt[i] > 1:
for k in range(1,rt[i]-1):
#print(k,tmp)
if tmp[k] >= rt[i] - k : j = rt[i] - k; i = i+k;break
else: rt.append(tmp[k])
else:
i = len(rt)
j = 0
else:
i += 1
j = 0
return rt
def saveHuman(p,v):
f = similarityDiff(p,v)
l = similarityDiff(p[::-1],v[::-1])[::-1]
rt = []
for i in range(len(f)):
if f[i] == len(v) or (i+len(v)-1 < len(l) and f[i] + l[i+len(v)-1] == len(v) -1): rt.append(i)
print(*rt,sep=' ')
for t in range(int(input())):
if t != 0: input()
p = input().strip()
v = input().strip()
saveHuman(p,v)
C rep HackerRank Solution
#include <malloc.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
struct bunch_t
{
char c;
int count;
};
void SaveHumanity( char * p, int p_len, int p_map, char * v, int v_len, int v_map , int farthest_chars[2][3] )
{
int i, j;
int mm1 = -1, mm2 = -1;
int idx1=-1;
int idx2=-1;
int print_space=0;
int mm[100001][2] ;
int next_match[100001];
int n=0;
int least_j = 0;
int num_comparisions=0;
int final_next_pos = -1;
memset( mm, -1, sizeof(mm));
for ( i = 2 ; farthest_chars[1][i] == -1 ; --i )
;
i = farthest_chars[1][i];
for ( i = (!i)?1:i ; i < v_len && i <= p_len-v_len ; ++i )
{ for ( j = 0 ; j < v_len-i ; ++j )
{
if ( v[j] == v[i+j] )
continue;
if ( mm[i][0] == -1 )
mm[i][0] = j;
else if ( mm[i][1] == -1 )
mm[i][1] = j;
else
break;
}
if ( j == v_len-i )
{ next_match[n] = i;
++n;
}
num_comparisions += j;
if ( num_comparisions > 5000000 )
{ final_next_pos = i+1;
break;
}
}
if ( final_next_pos == -1 )
final_next_pos = i;
for ( i = 0 ; i <= p_len - v_len ; )
{ int n1;
int next_pos;
for ( j = v_len - 1 ; j >= least_j && mm2 == -1 ; --j )
{ if ( p[i+j] != v[j] )
{
if ( mm1 != -1 )
{ if ( mm1 == i+j )
continue;
mm2 = i+j;
}
else
mm1 = i+j;
if (!( (1 << (p[i+j] - 'a' )) & v_map ))
{ if ( idx1 == -1 )
idx1 = i+j;
else
idx2 = i+j;
}
}
}
if ( mm2 == -1 )
{
if ( print_space )
printf(" ");
else
print_space=1;
printf("%d", i);
for ( n1 = 0 ; n1 < n ; ++n1 )
{ next_pos = next_match[n1];
#define is_null(mm) ( mm == -1 )
#define is_overtaken(mm) ( mm < i+next_pos )
#define is_nullified(mm) ( p[mm] == v[mm-i-next_pos ] )
if ( is_null (mm[next_pos][0]) || is_nullified( i + next_pos + mm[next_pos][0] ) && ( is_null( mm[next_pos][1] ) || is_nullified( i + next_pos + mm[next_pos][1] ) ) )
{ if ( is_null ( mm1 ) || is_overtaken( mm1 ) || is_nullified ( mm1 ) )
mm1 = -1;
break;
}
else
{ //mm[0] holds now
if ( is_null ( mm[next_pos][1] ) || is_nullified( i + next_pos + mm[next_pos][1] ) )
{ if ( is_null ( mm1 ) || is_overtaken(mm1) || is_nullified( mm1 ) || mm1 == i + next_pos + mm[next_pos][0] )
{ // mm[0] holds now
mm1 = i + next_pos + mm[next_pos][0] ;
break;
}
else
{ // mm[0] && mm1 hold now and are distinct
continue;
}
}
//mm[0] && mm[1] both hold now
else if ( is_nullified( i + next_pos + mm[next_pos][0] ) )
{
if ( is_null ( mm1 ) || is_overtaken(mm1) || is_nullified( mm1 ) || mm1 == i + next_pos + mm[next_pos][1] )
{ // mm[0] holds now
mm1 = i + next_pos + mm[next_pos][1] ;
break;
}
else
{ // mm[0] && mm1 hold now and are distinct
continue;
}
}
else
continue;
}
}
if ( n1 == n )
{ next_pos = final_next_pos;
least_j = 0;
}
else
{
least_j = v_len - next_pos;
}
if ( is_null ( mm1 ) || is_overtaken ( mm1 ) )
{ idx1 = -1; mm1 = -1;
}
i += next_pos;
}
else if ( idx2 != -1 )
{ if ( idx1 > idx2 )
{ i = idx2 + 1;
mm1 = idx1 ;
}
else
{ i = idx1 + 1;
idx1 = mm1 = idx2;
}
mm2 = -1;
idx2 = -1;
least_j = 0;
}
else
{
do
{ ++i;
} while ( idx1 != -1 && idx1 > i && p[i] != v[0] );
if ( idx1 == -1 || idx1 < i )
mm1 = idx1 = -1;
else
mm1 = idx1;
mm2 = -1;
least_j=0;
}
}
printf("\n");
}
int main( int argc, char * argv[] )
{
char * p;
char * v;
int p_map, v_map;
int p_len, v_len;
int t;
p = malloc( 100001 );
v = malloc( 100001 );
scanf("%d", &t);
while (t-- )
{ char c=0;
int farthest_chars[2][3] = { { -1, -1, -1 }, {-1, -1, -1} };
int unique_chars[2] ={ 0, 0};
unsigned char chars_recvd[2][26] = {{0}};
struct bunch_t chain[2][100000] = {{0},{0}};
int chain_top[2] = {0,0};
int plag, vlag;
int po, vo;
int pb, vb;
int start_pb;
int pc, vc;
int mm1;
int space_char=0;
p_len=0;
p_map = 0;
v_map = 0;
getchar();
while ( (c=getchar()) != '\n' )
{ p[p_len] = c;
if ( chain[0][ chain_top[0] ].c == c )
++chain[0][ chain_top[0] ].count ;
else
{ ++chain_top[0];
chain[0][ chain_top[0] ].c = c;
chain[0][ chain_top[0] ].count = 1;
}
if ( ! chars_recvd[0][c-'a'] )
{ chars_recvd[0][ c - 'a' ] = 1;
++unique_chars[0];
farthest_chars[0][2] = farthest_chars[0][1];
farthest_chars[0][1] = farthest_chars[0][0];
farthest_chars[0][0] = p_len;
}
++p_len;
p_map |= (1 << ( c-'a'));
}
p[p_len] = 0;
v_len=0;
while ( (c=getchar()) != '\n' )
{ v[v_len] = c;
if ( chain[1][ chain_top[1] ].c == c )
++chain[1][ chain_top[1] ].count ;
else
{ ++chain_top[1];
chain[1][ chain_top[1] ].c = c;
chain[1][ chain_top[1] ].count = 1;
}
if ( ! chars_recvd[0][ c - 'a' ] )
++unique_chars[1];
if ( ! chars_recvd[1][c-'a'] )
{ chars_recvd[1][ c - 'a' ] = 1;
farthest_chars[1][2] = farthest_chars[1][1];
farthest_chars[1][1] = farthest_chars[1][0];
farthest_chars[1][0] = v_len;
}
++v_len;
v_map |= (1 << (c-'a'));
}
v[v_len] = 0;
if ( unique_chars[1] > 1 || p_len < v_len || chain_top[0] < chain_top[1]-2 )
printf("\n");
else if ( chain_top[0] <= 14000 )
{
plag = vlag = 0;
start_pb = 1;
po = vo = 0;
while ( po <= p_len - v_len )
{ pb = start_pb;
vb = 1;
mm1 = 0;
pc = chain[0][pb].count;
vc = chain[1][vb].count;
vo = 0;
while ( vc )
{ if ( chain[0][pb].c == chain[1][vb].c )
{ if ( pc < vc )
{ vc -= pc;
vo += pc;
++pb;
pc = chain[0][pb].count;
}
else if ( pc > vc )
{ pc -= vc;
vo += vc;
++vb;
vc = chain[1][vb].count;
}
else
{ ++vb;
++pb;
vo += vc;
vc = chain[1][vb].count;
pc = chain[0][pb].count;
}
}
else
{ // chars are different
if ( mm1 )
{
break;
}
else
{ mm1 = 1;
--pc;
--vc;
++vo;
if ( ! pc )
{ ++pb;
pc = chain[0][pb].count;
}
if ( ! vc )
{ ++vb;
vc = chain[1][vb].count;
}
}
}
}
if ( ! vc )
{ if ( space_char )
printf(" %d", po );
else
{ printf("%d", po );
space_char=1;
}
}
++po;
if ( chain[0][start_pb].count > 1 )
--chain[0][start_pb].count;
else
++start_pb;
}
printf("\n");
}
else
SaveHumanity( p, p_len, p_map, v, v_len, v_map, farthest_chars );
}
return 0;
}
Comments 1