Computing the largest substring starting with a substring

Question

Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.

• sub_sandwich("catcowcat", "cat") → 9
• sub_sandwich("catcowcat", "cow") → 3
• sub_sandwich("cccatcowcatxx", "cat") → 9

I'm not very satisfied with my code and I'm not sure how I can improve it.

def subSandwich(word, char, pos, start, end):
 if pos == len(word)-1:
 if end == 0:
 return len(char)
 return end - (start-2)
 if word[pos:pos+len(char)] == char:
 if start != 0:
 end = pos + len(char) - 1
 else:
 start = pos+1
 return subSandwich(word, char, pos + 1, start, end) 
def main():
 print subSandwich("catcowcat", "cow",0,0,0)
if __name__ == "__main__":
 main()

• nhgrif: Your acceptance criteria (and therefore any unit tests) seems incomplete. What is the expected return for a 0-length string? 0-length substring? Non-0-length of each but substring not found in string?
• janos: For input "catcowcat", "abc" I would expect 0 as output, but that's not what happens. When the search string is not found, the algorithm returns the length of the search string. I'm not sure what's the sense in that.
• 200_success: Why should recursion be used at all? It should be pretty simple with str.index() and s.rindex().

Answer 1

Revise the sub for simplicity with only 2 parameters, reducing 1 char from both end at 1 loop.

#!/usr/bin/python
import unittest
import sys
import os
def subSandwich_new(word, char):
 num = word.count(char)
 if num ==0:
 return 0
 elif num ==1:
 return len(char)
 else:
 # first string with length of char
 first = word[:len(char)]
 match = 0
 if first == char:
 match = match + 1
 else:
 # remove 1 char from word
 word = word[1:]
 # string from end with the length of char
 last = word[-len(char):]
 if last == char:
 match = match + 1
 else:
 # removing 1 char from word
 word = word[:-1]
 if match ==2:
 # first and last both match
 return len(word)
 else:
 return subSandwich_new(word, char)
class SandwichTestNew(unittest.TestCase):
 def test_subSandwich_new(self):
 result = subSandwich_new('catcowcat', 'cat')
 self.assertEqual(result, 9)
 def test_subSandwich_new2(self):
 result = subSandwich_new('catcowcat', 'cow')
 self.assertEqual(result, 3)
 def test_subSandwich_new3(self):
 result = subSandwich_new('ccatcowcatxx', 'cat')
 self.assertEqual(result, 9)
 def test_subSandwich_new4(self):
 result = subSandwich_new('cat', 'cat')
 self.assertEqual(result, 3)
 def test_subSandwich_new5(self):
 result = subSandwich_new('cat', 'cow')
 self.assertEqual(result, 0)

Answer 2

In no particular order:

• If you go down the recursion route, provide default parameters for the pos, start, and end parameters, like so:

  def subSandwich(word, char, pos=0, start=0, end=0)
  

  If I want to use it as-is, I have to provide 0,0,0 on my first call. That’s exposing unnecessary implementation details to your users.

• If the string isn’t found, you return the length of the search string, e.g.:

  >>> subSandwich("catcowcat", "fish")
  4
  

  It would be better to either return 0 (because you don’t find a matching string), or raise an appropriate exception that says "the string wasn’t found".

• Style issues: read PEP 8. In particular, snake_case for function names, and spaces around commas and operators.

• Put some comments in your code. It’s not immediately obvious what the different variables mean, so it’s hard for me to tell what it’s supposed to be doing (and by extension, whether it’s doing it correctly).

  You should always have docstrings on user-facing functions.

• Use better variable names: the name "char" sounds like it’s a string of length 1, whereas it can actually be a string of arbitrary length. You could use the suggested variable name from the question text:

  def sub_sandwidth(text, sub, pos=0, start=0, end=0)
  

  Note that I’ve used "text", not "string", for the first argument, to avoid confusion with the builtin string module.

• You’re mostly varying the pos parameter, and rarely touch the start or end parameters. A tidier recursion might involve just passing around the two strings, and slowly cutting the size of the text variable until it matches. This would allow you to use the startswith() and endswith() methods, which IMO are a little neater.

  Here’s how I’d rewrite the function that way:

  def sub_sandwich(text, sub):
   """
   Returns the length of the largest substring of `text` that both
   starts and ends with `sub`.
   Returns 0 if `sub` is not present in `text`.
   """
   # The empty string cannot have any substrings
   if not text:
   return 0
   if text.startswith(sub) and text.endswith(sub):
   return len(text)
   elif text.startswith(sub):
   return sub_sandwich(text[:-1], sub)
   else:
   return sub_sandwich(text[1:], sub)