Created
January 3, 2014 05:35
-
-
Save philippbayer/8233341 to your computer and use it in GitHub Desktop.
My solution for "String Similarity" for HackerRank
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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