PrivacyScanData/Hash/matching_with_mismatches.py

# python3

import sys
import random
import fileinput

## fro preComputeHash and getHashValue function refer to the 4th program - substring equality
## compute the hash values for all the combinations in the given string
def preComputeHash(string, m, x):
    string_length = len(string)
    hash_values = [0]
    for i in range(1, string_length + 1):
		# subtracting the ASCII code of 'a' to maintain the value of the strings within 0 to 26
        val = ((x * hash_values[i - 1]) % m + (ord(string[i - 1]) - ord('a')) % m) % m
        hash_values.append(val)
    return hash_values

## return the hash value using the precomputed hash values of the given index and length
def getHashValue(hash_values, index_start, length, x, m, power_multiplier):
	return (hash_values[index_start + length] % m - (power_multiplier * hash_values[index_start]) % m) % m


"""
	Precompute power of X with module of M1 and M2. It can buy you extra time when you try 
	to compute hash of substring. Otherwise, it will cost you extra O(log(n)) for pow(X, n, M).
"""
def getPower(x,length,m):
	pow_lst = []
	for i in range(length+1):
		pow_lst.append(pow(x,i,m))
	return pow_lst



class Mismatches:
	def __init__(self, text, pattern):
		self.text = text
		self.pattern = pattern
		self.m1 = pow(10, 15) + 7
		self.m2 = pow(10, 15) + 456
		self.x = 26

		self.pattern_length = len(pattern)

		self.hash_values_t1 = preComputeHash(self.text, self.m1, self.x)
		self.hash_values_t2 = preComputeHash(self.text, self.m2, self.x)

		self.hash_values_p1 = preComputeHash(self.pattern, self.m1, self.x)
		self.hash_values_p2 = preComputeHash(self.pattern, self.m2, self.x)

		self.power_lst_m1 = getPower(self.x, self.pattern_length, self.m1)
		self.power_lst_m2 = getPower(self.x, self.pattern_length, self.m2)

	def solve(self, k, text, pattern):
		pattern_length = len(pattern)
		text_length = len(text)
		result = []
		for i in range(text_length-pattern_length+1):
			value = self.checkMatches(text[i:i+pattern_length], pattern, k, i, i+pattern_length, 0, pattern_length)
			if value <= k:
				result.append(i)
		return result


	def checkMatches(self, subtext, pattern, k, start_index_t, end_index_t, start_index_p, end_index_p):
		mismatch_count = 0

		left = 0
		right = len(pattern)
		mid = left + (right - left)//2
		#print("    ",subtext, pattern, start_index_t, end_index_t, start_index_p, end_index_p)  #left, right, mid, mismatch_count)


		if mid == 0:
			if ord(subtext) != ord(pattern):
				return 1
			else:
				return 0

		if self.checkHash(start_index_t, end_index_t, start_index_p, end_index_p):
			#mismatch_count = mismatch_count + self.checkMatches(subtext[mid:right], pattern[mid:right], k)
			return mismatch_count
		else:
			mid_index_t = (start_index_t + end_index_t)//2  ## uses this index to get the has values of the pattern from the original text
			mid_index_p = (start_index_p + end_index_p)//2  ## keep track of the index for the pattern to get the hash values
			mismatch_count = self.checkMatches(subtext[left:mid], pattern[left:mid], k, start_index_t, mid_index_t, start_index_p, mid_index_p) + \
							 self.checkMatches(subtext[mid:right], pattern[mid:right], k, mid_index_t, end_index_t, mid_index_p, end_index_p)
			return mismatch_count
		#return mismatch_count



	def checkHash(self, index_start_t, index_end_t, index_start_p, index_end_p):
		length = index_end_t - index_start_t
		hash_value_st1 = getHashValue(self.hash_values_t1, index_start_t, length, self.x, self.m1, self.power_lst_m1[length])
		hash_value_st2 = getHashValue(self.hash_values_t2, index_start_t, length, self.x, self.m2, self.power_lst_m2[length])

		hash_value_sp1 = getHashValue(self.hash_values_p1, index_start_p, length, self.x, self.m1, self.power_lst_m1[length])
		hash_value_sp2 = getHashValue(self.hash_values_p2, index_start_p, length, self.x, self.m2, self.power_lst_m2[length])

		return (hash_value_st1 == hash_value_sp1 and hash_value_st2 == hash_value_sp2)


for line in fileinput.input():
	if line != '\n':
		k, t, p = line.split()
		process = Mismatches(t,p)
		ans = process.solve(int(k), t, p)
		print(len(ans), *ans)