Group Shifted String

ALPHA = 26

def getDiffString(str):

shift=""

for i in range(1, len(str)):

dif = (ord(str[i]) -

ord(str[i - 1]))

if(dif < 0):

dif += ALPHA

shift += chr(dif + ord('a'))

return shift

def groupShiftedString(str,n):

groupMap = {}

for i in range(n):

diffStr = getDiffString(str[i])

if diffStr not in groupMap:

groupMap[diffStr] = [i]

else:

groupMap[diffStr].append(i)

for it in groupMap:

v = groupMap[it]

for i in range(len(v)):

print(str[v[i]], end = " ")

print()

str = ["acd", "dfg", "wyz",

"yab", "mop","bdfh",

"a", "x", "moqs"]

n = len(str)

groupShiftedString(str, n)

Moser-de Bruijn Sequence

def gen(n):

if n == 0:

return 0

elif n ==1:

return 1

elif n % 2 ==0:

return 4 * gen(n // 2)

elif n % 2 == 1:

return 4 * gen(n // 2) +1

def moserDeBruijn(n):

for i in range(n):

print(gen(i), end = " ")

n = 15

print("First", n, "terms of ",

"Moser-de Bruijn Sequence:")

moserDeBruijn(n)

Calculate City Block Distance

import numpy as np

def cityblock_distance(A, B):

result = np.sum([abs(a - b) for (a, b) in zip(A, B)])

return result

if __name__== "__main__":

arr1 = [5,2]

arr2 = [1,5]

result = cityblock_distance(arr1, arr2)

print(result)

Calculate the Euclidean distance using NumPy

 Using square() and sum() 

import numpy as np

point1 = np.array((5,2))

point2 = np.array((1,5))

sum_sq = np.sum(np.square(point1 - point2))

print(np.sqrt(sum_sq))

Finite Automata algorithm for Pattern Searching

NO_OF_CHARS = 256

def getNextState(pat, M, state, x):

if state < M and x == ord(pat[state]):

return state+1

i=0

for ns in range(state,0,-1):

if ord(pat[ns-1]) == x:

while(i<ns-1):

if pat[i] != pat[state-ns+1+i]:

break

i+=1

if i == ns-1:

return ns

return 0

def computeTF(pat, M):

global NO_OF_CHARS

TF = [[0 for i in range(NO_OF_CHARS)]\

for _ in range(M+1)]

for state in range(M+1):

for x in range(NO_OF_CHARS):

z = getNextState(pat, M, state, x)

TF[state][x] = z

return TF

def search(pat, txt):

global NO_OF_CHARS

M = len(pat)

N = len(txt)

TF = computeTF(pat, M)

state=0

for i in range(N):

state = TF[state][ord(txt[i])]

if state == M:

print("Pattern found at index: {}".\

format(i-M+1))

def main():

txt = "AABAACAADAABAAABAA"

pat = "AABA"

search(pat, txt)

if __name__ == '__main__':

main()