3

I'm following a python website for my schoolwork. It's really neat, it gives you tasks to complete and compiles the code in the browser. Anyway, I came to a challenge that I'm not really sure how to go about.

One of the questions was:

The same substring may occur several times inside the same string: for example "assesses" has the substring "sses" 2 times, and "trans-Panamanian banana" has the substring "an" 6 times. Write a program that takes two lines of input, we call the first needle and the second haystack. Print the number of times that needle occurs as a substring of haystack.

I'm not too sure how I should start this, I know I have to compare the two strings but how? I used the count method, but it didn't recognize the second occurrence of sses in assesses.

My second question is one I solved but I cheated a little.

The question was:

Write a program that takes a single input line of the form «number1»+«number2», where both of these represent positive integers, and outputs the sum of the two numbers. For example on input 5+12 the output should be 17.

I used the eval() method and it worked, I just think that this wasn't what the grader had in mind for this.

Any insight would be greatly appreciated.

EDIT: Second question was solved.

Mike
  • 47,263
  • 29
  • 113
  • 177
Thegluestickman
  • 301
  • 1
  • 5
  • 16
  • The reason `str.count()` didn't work is that it doesn't count overlapping occurrences. – Gareth Latty May 25 '12 at 22:55
  • 3
    Also, if you have two questions, ask two questions, don't group them together into a single question. – Gareth Latty May 25 '12 at 22:56
  • @Lattyware I had a feeling that was the reason, because for the next occurrence it worked fine. – Thegluestickman May 25 '12 at 22:56
  • Re: the second question- one way to think of it is, what do you do as a human-computer when you're presented with "5+12"? How do you figure out how to compute it? – Karmel May 25 '12 at 23:00
  • @Karmel I got it! I iterated through all of the values between zero and the length of the string. Then took the number that made s[i] = "+" – Thegluestickman May 25 '12 at 23:15
  • 1
    @Thegluestickman :) And once you get the hang of the logic, you can find optimizations. In this case, there's a .split() method in Python that is handy. Try `'5+2'.split('+')` – Karmel May 25 '12 at 23:45

9 Answers9

3

For the first question, str.count() does not find overlapping matches, as you noticed. Instead, use str.find() and advance your starting index after each time you find a match, until the result is -1, for example:

>>> 'assesses'.find('sses', 0)    # first look at the start of the string
1
>>> 'assesses'.find('sses', 2)    # now look at previous index + 1
4
>>> 'assesses'.find('sses', 5)    # now look at previous index + 1
-1

Since there were two results before we got -1, we know that there are two locations to find 'sses' in 'assesses'.

For you second question, you will need to split() the string on '+', which will give you a list of two strings. Call int() on each of them, and then add them together.

Andrew Clark
  • 202,379
  • 35
  • 273
  • 306
  • I don't quite understand the find method you're using. If I understand, you're taking the first string and finding the next within the string. What I don't understand is the step pattern afterwards. – Thegluestickman May 25 '12 at 23:26
  • @Thegluestickman - `assesses.find('sses', 0)` is the starting point, that returns 1 so we know that the substring can be found at index 1. Now we want to see if it can be found at a later index, so we start from index 2. Since `assesses.find('sses', 2)` returns 4, when we try again we want to start at index 5, since that is one after the previous match. – Andrew Clark May 25 '12 at 23:49
2

This is what you are looking for on question 1:

needle = input()    #defines first input string
haystack = input()    #defines second input string
times = 0     #defines number of times first input string is in second
for a in range(0, len(haystack) - 1):     #loop to check strings within haystack
    if haystack[a:len(needle) + a] == needle:     #checking for needle in haystack
        times = times + 1     #increasing our number of occurances if true
print(times)     #and here is your output
Leiv
  • 21
  • 2
1

For the second question I got:

S = input()
x = S.find('+')
print(int(S[0:x])+(int(S[x+1:])))
UnseenAlchemist
  • 11
  • 1
1

Two strings of input, one counter for totaling the number of occurrences, one variable named indx that will always be the starting search point, one loc variable that will be the (of int type) index location of the beginning of any occurrence of str1 in str2

str1 = input() #input 1
str2 = input() #input 2
count=0  #occurrence counter
indx=0  #index of string to start search at
for i in str2:  #for character i in input 2
    loc = str2.find(str1, indx)  #starting index of occurrence
    if loc == -1:  #-1 means there were no occurences
        break  #in this case break the search
    indx=loc+1  #to find the next occurrence, the new starting point will be the starting location of the last occurrence + 1
    count=count+1  #add an occurrence
print(count) #voila!
user7674511
  • 11
  • 2
0

  1. the STRING.count method should work just fine for the first problem. If you look carefully, there actually aren't two non-overlapping 'sses' strings in assesses.

    You either have a- sses -ses, or asse- sses. Do you see the issue? Calling "trans-Panamanian banana".count("an") produces the correct number.

  2. I think using eval() is probably ok. Your other option is to split on the + and then iterate over the resulting list, doing type conversion and accumulation as you go. It sounds like your doing a string module, so that might be the better solution for your gpa ;).

EDIT: F.G. beat me to posting essentially the same answer by mere seconds. Gah!

Community
  • 1
  • 1
Maus
  • 1,791
  • 1
  • 17
  • 28
0

  1. see: string count with overlapping occurrences

  2. sum( map(lambda val: int(val.strip()), INPUT.split("+")))

Community
  • 1
  • 1
ddzialak
  • 1,042
  • 7
  • 15
0

For the first question you could also use this sample code:

def occurs(string, sub):
count = start = 0
while True:
    start = string.find(sub, start) + 1
    if start > 0:
        count+=1
    else:
        return count

It will solve your problem.

heretolearn
  • 6,387
  • 4
  • 30
  • 53
0

Answer for the first question:

needle=input()
haystack=input()
counter=0
for i in range(0,len(haystack)):
  if(haystack[i:len(needle)+i]!=needle):
     continue
  counter=counter+1
print(counter)

Answer for the second question:

S = input()
for position in range(0, len(S)):
plus=S[position]
    if (plus!="+"):
      continue
    number1=int(S[0:position])
    number2=int(S[position+1:len(S)])
    print(number1+number2)
0

I found answer for second question:

S=input()
x=len(S)
for i in range (0,x):
   w= S[i]
   if w == '+': 
      a=(S[0:i])
      b=(S[i+1:x])
      u=int(a)
      o=int(b)
      p=u+o
      print(p)
Szymon
  • 1