Count amount of comparison using naive string matching algorithm python

Question

In my code I try to found index of the pattern, count every comparison and I also want to stop this algorithm then my pattern is too long for comparison to rest of the text. Something is wrong with counter and I couldn't stop algorithm. I am beginner and I don't have idea what to do.

def search(W, T):
    count = 0
    for i in range(len(T) - len(W) + 1):
        if i > len(T)-len(W):
            break
        j = 0
        while(j < len(W)):
            if (T[i  + j] != W[j]):
                count += 1
                break
            j += 1
            
        if (j == len(W)):
            count += len(W)
            print("Pattern found at index ", i, count)
 
if __name__ == '__main__':
    T = "AABAACAADAABAAABAA"
    W = "AABA"

    search(W, T)

Thanks for helping.

I expect that someone will change my code or tell me what to do.

Ilia Nechaev · Accepted Answer · 2022-11-04 12:57:14Z

First of all, as you are a beginner in Python here's some tips:

You do not need brackets in if: if j == len(W): is ok, moreover these brackets are against PEP8 codestyle.
You don't need this condition:

    if i > len(T)-len(W):
        break

range() is smart guy. He won't let i be more then len(T)-len(W)

Now to your question, here's the solution (I hope, that I understand what do you want)

def search(W, T):
    count = 0
    for i in range(len(T) - len(W) + 1):
        j = 0
        while j < len(W):
            if T[i + j] != W[j]:
                count += 1
                break
            j += 1
            count += 1

        if j == len(W):
            print("Pattern found at index ", i, count)


if __name__ == '__main__':
    T = "AABAACAADAABAAABAA"
    W = "AABA"

    search(W, T)

The problem was that you increment your counter only when you founded the pattern or when you failed to find it. Here's example:

T = AAABAAA

W = AABA

In your solution counter would be incremented only on the 3d letter "A" while it should be incremented after each comparison.

I hope everything is clear. Good luck in studying!

Collectives™ on Stack Overflow

Count amount of comparison using naive string matching algorithm python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related