For string similarity, it is defined as longest common prefix length. For example, "abc" and "abd" is 2, and "aaa" and "aaab" is 3.
The problem is calculate the similarity of string S and all its suffixes, including itself as the first suffix.
For example, for S="ababaa", suffixes are "ababaa", "babaa", "abaa","baa","aa" and "a", the similarity are 6+0+3+0+1+1=11.
My code works and I am looking for smarter ideas to be more efficient.
# Complete the function below. from collections import defaultdict class TrieNode: def __init__(self): self.children=defaultdict(TrieNode) self.isEnd=False class TrieTree: def __init__(self): self.root=TrieNode() def insert(self, word): node = self.root for w in word: node = node.children[w] node.isEnd = True def search(self, word): node = self.root count = 0 for w in word: node = node.children.get(w) if not node: break else: count += 1 return count def StringSimilarity(inputs): resultFormat= for word in inputs: # build Trie tree index = TrieTree() index.insert(word) result = 0 # search for suffix for i in range(len(word)): result += index.search(word[i:]) print result resultFormat.append(result) return resultFormat