Find a string in a string - Python

Question

I am trying to implement a function that find a text in a string recursively.

I tried this, but I don't know why it's not working. Please note that I am new to coding.

def find(text, substring):
  if len(text) == 0:
     return 0
  while substring[0] in text:
     return find(text, substring[1:])

Thanks! :)

Example:

find("mississippi", "sip")
True
find("to be or not to be", "be")
True
find("mississippi", "sup")
False

What is the expected result, and what is the result you're getting? — KSFT, Mar 28 '15 at 22:19
You have a base case for when the end of the string is reached, but you also need a base case for when a match has been found. — Greg Prisament, Mar 28 '15 at 22:21
@GregPrisament Do you mean "for when a match hasn't been found"? — KSFT, Mar 28 '15 at 22:22
Finding a substring fast isn't a completely trivial task, a recursive algorithm results in *O(n^2)* algorithm. Using the *Knuth-Patterson* algorithm, one can achieve *O(n)* linear time. — Willem Van Onsem, Mar 28 '15 at 22:25

score 1 · Answer 1 · edited May 23 '17 at 12:30

1

There are much simpler ways to do this. For example, you can loop over the indices of the string and check if the substring is at that location, as mentioned here:

[i for i in range(len(string)) if s.startswith(substr,i)]

This will evaluate to a list of indices of all of the occurrences of substr in string.

edited May 23 '17 at 12:30

Community

1
1

answered Mar 28 '15 at 22:29

KSFT

1,774
11
17

score 0 · Answer 2 · answered Mar 28 '15 at 22:21

0

You need a base case for your recursive function that will eventually return without recursing. Your base case len(text)==0 is never executed unless text=='' the first time through.

answered Mar 28 '15 at 22:21

Bennett Brown

5,234
1
27
35

There is a base case. If a function doesn't run a `return` statement, then it will return `None`. – KSFT Mar 28 '15 at 22:22
@KSFT, yes. OP needs to clartify what desired result is; this function never returns True. – Bennett Brown Mar 28 '15 at 22:24

score 0 · Answer 3 · answered Mar 28 '15 at 22:40

If I understand your question correctly, you want to implement a recursive function where find(text, substring), given two strings, returns the same result as the simple Python expression substring in text. A recursive breakdown of this problem would be:

Does text begin with substring? If so, return True. (Base case 1)
Is text empty? If so, return False. (Base case 2).
Otherwise, return the result of find(text[1:], substring) – the recursive case where we call the same function on a smaller problem.

See if you can implement that! For base case one, you'll have good use of Python's String method startswith (google it!).

Find a string in a string - Python

3 Answers3