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

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