brute force pattern matching algorithm

general
1

in the brute force pattern matching algorithm when all the characters in the pattern are unique then brute force can be implemented in Big-oh(n) complexity where n is the length of the string( reference :introduction to algorithms).
can anyone help me with the algorithm? thanks in advance

2

Yes we can do pattern Matching in O(n) Complexity given that all the characters in the pattern are unique.

Algorithm (self explanatory python Code):

Let the pattern be P of Length PL and Source String be S of Length SL

S = raw_input()
P = raw_input()
SL = len(S)
PL = len(P)
if PL > SL:
	print("No Match Found")
else:
	Found = False
	for i in range(0,SL):
		j = 0
		while j < PL and S[i] == P[j] :
			i=i+1
			j=j+1
		if j == PL:
			Found = True
			print("Matching Found At " + str(i-PL+1))
	if not Found:		
		print("No Matching Found")

Code prints all the positions where the pattern starts

1 Like