Hackers Ranking String Similarity

I am currently trying to teach myself some programming. I have started to work with Python by doing this challenge.

For each test case, I need to find the sum of the self-similarities of a string with each of its suffixes. For example, given the string ababaa, the self-similarity scores are

• 6 (because ababaa = ababaa)

• 0 (because ababaa ≠ babaa)

• 3 (because ababaa and abaa share three initial characters)

• 0 (because ababaa ≠ baa)

• 1 (because ababaa and aa share one initial character)

• 1 (because ababaa and a share one initial character)

… for a total score of 11.

When I test run it works out fine, however when I run this code with longer strings it takes too long time to run, so the site shuts down the program. Each input string consists of up to 100000 lowercase characters.

Is this because this code make unnecessary loops? Or what else might the problem be here?

# Solution.py for https://www.hackerrank.com/challenges/string-similarity
import sys
for line in sys.stdin:
  if line.islower():
    line = line[:-1] # line will be compared to suffix
    line_length = len(line)
    points = 0
    for s in xrange(0,line_length):
      suffix = line[s:]
      suffix_length = len(suffix)
      count = 1
      while count < suffix_length+1:
        if line.startswith(suffix[:1]): # if line and first character of suffix mach
          if line.startswith(suffix[:suffix_length]):
            points += len(suffix[:suffix_length])
            break
          else:
            if line.startswith(suffix[:count+1]):
              count += 1
            elif line.startswith(suffix[:count]):
              points += len(suffix[:count])
              break
        else:
          break
    print points

It is slow because you use slow algorithm ("too many loops"). This problem might be a bit hard for beginner. If you want to solve it anyway, be sure to search for tutorials on string algorithms (try to look at http://en.wikipedia.org/wiki/Aho-Corasick and change it a bit). Maybe dynamic programming will help you with this or other problems.

PS I hope you understand nobody here can not spoil the solution. Have fun with programming.

You could always try another problems:

Timus one of the best: http://acm.timus.ru/problemset.aspx

Project Euler if you like mathematics: http://projecteuler.net/

(Please feel free to edit and add some more.)

StackExchange Code Review Q#24246, answer score: 4