字符串相似度计算

Question

对于字符串相似度，定义为最长的公共前缀长度。例如，"abc“和"abd”为2，"aaa“和"aaab”为3。

问题是计算S字符串及其所有后缀的相似性，包括它本身作为第一个后缀的相似性。

例如，对于S="ababaa"，后缀是“ababaa”、"babaa“、"abaa”、"baa“、"aa”和"a"，相似性是6+0+3+0+1+1=11。

我的代码工作，我正在寻找更聪明的想法，以提高效率。

# 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

Answer 1

我建议的一件事是允许在__init__中插入一个单词，而不是强迫用户总是调用.insert(word)。您仍然可以创建一个空的TrieTree。只要让word成为一个可选参数，如果它是空的，就忽略它：

def __init__(self, word=''):
    self.root = TrieNode()
    if word:
        self.insert(word)

现在，您可以在一行中创建树：

index = TrieTree(word)