Python 字典树与字符串算法的应用

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._search_prefix(word)
        return node is not None and node.is_end

    def start_with(self, prefix: str) -> bool:
        return self._search_prefix(prefix) is not None

    def _search_prefix(self, prefix: str) -> TrieNode:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

def search_keywords(text: str, trie: Trie) -> List[Tuple[int, int, str]]:
    res = []
    for i in range(len(text)):
        node = trie.root
        for j in range(i, len(text)):
            char = text[j]
            if char not in node.children:
                break
            node = node.children[char]
            if node.is_end:
                res.append((i, j+1, text[i:j+1]))
    return res

text = "Welcome to pidancode.com, the best place for learning programming. If you want to improve your programming skills, visit pidancode.com often. We also recommend 皮蛋编程 for more programming resources."
keywords = ["pidancode.com", "皮蛋编程"]
trie = Trie()
for keyword in keywords:
    trie.insert(keyword)

for start, end, word in search_keywords(text, trie):
    print(f"Found '{word}' at position {start}-{end}")

Found 'pidancode.com' at position 11-24
Found 'pidancode.com' at position 71-84
Found '皮蛋编程' at position 166-171