CODEWITHSUNDEEP
pythonpython-3.x
chopper draw lion4
chopper draw lion4

Reputation: 13507

Recreating builtin s.find('substring') function

I am trying to recreate the s.find('substring') function. the two problems I am encountering are as follows:
1)The ability to find the beginning index, for example: 

Enter a phrase please"my best test ever!"
Enter a word you wish to find"best"
found first instance of letter at,  0
found first instance of letter at,  19
>>>

2) Assuming the correct index has been located, I expected this code segment to indicate whether or not the entire substring is within the string:

str2 in str1[i:len(str1)]

Whenever I test it independently of the main loop in idle, it does not work correctly.

Here is my main code: 

str1 = input("Enter a phrase please")
str2 = input("Enter a word you wish to find")




for i in range(len(str1)):
    if str2[0] == str1[i]:
        print("found first instance of letter at, ", i)
        str2 in str1[i:len(str1)]

Any suggestions would be greatly appreciated, thanks mates!

Upvotes: 1

Views: 107

Answers (2)

dawg
dawg

Reputation: 104072

If you want a demo of an algorithm that does not use any of the wonderful tools that Python gives you, take a look at the Knuth-Morris-Pratt method.

Here, roughly implemented in Python as if Python were Assembly:

  #0         1         2
  #0123456789012345678901234
S='dcdcacdcdeerecdabcddfdabc'
W=               'abc' # ^^^
m=0
i=0
while True:
    if m+i==len(S):
        break   
    if W[i]==S[m+i]:
        if i==len(W)-1:
            print 'MATCH!', m
            i=0
            m+=1
        else:
            i+=1
    else:
        i=0
        m+=1

Prints:

MATCH! 15
MATCH! 22

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1124110

Your loop should work just fine, but you are not doing anything with the str2 in str1[..] test and are not calculating the end point correctly; you want to use the length of str2 here, really.

You could loop directly over str1 and add indices with the enumerate() function. You need to add the len(str2) result to i to find the endpoint, and make it print out the test; I used == here as the resulting slice should be the same string:

for i, char in enumerate(str1):
    if str2[0] == char:
        print("found first instance of letter at,", i)
        print(str2 == str1[i:i + len(str2)])

Demo:

>>> str1 = 'my best test ever!'
>>> str2 = 'best'
>>> for i, char in enumerate(str1):
...     if str2[0] == char:
...         print("found first instance of letter at, ", i)
...         print(str2 == str1[i:i + len(str2)])
... 
found first instance of letter at,  3
True

Upvotes: 2

Related Questions