Skip to content

Instantly share code, notes, and snippets.

@philippbayer
Created January 3, 2014 05:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save philippbayer/8233341 to your computer and use it in GitHub Desktop.
Save philippbayer/8233341 to your computer and use it in GitHub Desktop.
My solution for "String Similarity" for HackerRank
def get_similarity(a, suffix):
from itertools import izip
score = 0
for a, b in izip(a, suffix):
if a != b:
break
score += 1
return score
def stringSimilarity(a):
# makes all possible suffixes for a string:
# ababaaa becomes ababaaa, babaaa, abaaa, baaa, aaa, aa, a
# and then counts how many prefixes between the suffix and the string are shared
# abaaaa shares 3 prefixes with ababaaa
# and sums up the shared prefixes
answer = 0
i = 0
while i < len(a):
suffix = a[i:]
answer += get_similarity(a, suffix)
i += 1
return answer
if __name__ == '__main__':
# example input:
# 2
# ababaa
# aa
# example output:
# 11
# 3
t = input() # number of strings to check
for i in range(0,t):
a=raw_input() # string to check
print stringSimilarity(a)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment