6
\$\begingroup\$

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 ababaababaa)
  • 3 (because ababaa and abaa share three initial characters)
  • 0 (because ababaabaa)
  • 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
\$\endgroup\$

migrated from programmers.stackexchange.com Mar 22 '13 at 11:38

This question came from our site for professionals, academics, and students working within the systems development life cycle.

4
\$\begingroup\$

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.)

\$\endgroup\$
1
\$\begingroup\$

You have far too many if line.startswith(something) checks inside the while loop -- you are checking the same characters many times. The while loop counts characters, so you only need to compare one pair of characters on each iteration.

\$\endgroup\$
0
\$\begingroup\$

As @Janne-Karila has said there are too many startswiths. Your suffix[:1] could be replaced by suffix[0] and suffix[:suffix_length] is simply the same as suffix.

If you design the loops right you only need to compare one character at a time, and there is no call to use startswith at all. This also greatly simplifies the code.

def string_sim():
    n = int(sys.stdin.readline())
    for _ in range(n):
        line = sys.stdin.readline().strip()
        points = len(line)
        for s in xrange(1, len(line)):
            for count in xrange(len(line) - s):
                if line[count] != line[s + count]:
                    break
                points += 1
        print points
string_sim()

This will give a slight speed boost, but as others have pointed out, you need a wholly better algorithm to pass all the tests.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy