Aho-Corasick用于部分文本匹配
创始人
2024-07-31 13:02:01
0

Aho-Corasick算法是一种多模式匹配算法,用于在一个文本中查找多个模式串的出现位置。下面是一个使用Aho-Corasick算法实现部分文本匹配的代码示例:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False
        self.failure_link = None
        self.output = []

class AhoCorasick:
    def __init__(self, patterns):
        self.root = TrieNode()
        self.build_trie(patterns)
        self.build_failure_links()

    def build_trie(self, patterns):
        for pattern in patterns:
            current_node = self.root
            for char in pattern:
                if char not in current_node.children:
                    current_node.children[char] = TrieNode()
                current_node = current_node.children[char]
            current_node.is_end_of_word = True
            current_node.output.append(pattern)

    def build_failure_links(self):
        queue = []
        for child_node in self.root.children.values():
            queue.append(child_node)
            child_node.failure_link = self.root
        
        while queue:
            current_node = queue.pop(0)
            for char, child_node in current_node.children.items():
                queue.append(child_node)
                failure_node = current_node.failure_link
                while failure_node and char not in failure_node.children:
                    failure_node = failure_node.failure_link
                
                if failure_node:
                    child_node.failure_link = failure_node.children[char]
                    child_node.output += failure_node.children[char].output

    def match(self, text):
        current_node = self.root
        matches = []

        for i, char in enumerate(text):
            while current_node and char not in current_node.children:
                current_node = current_node.failure_link
            if not current_node:
                current_node = self.root
                continue
            
            current_node = current_node.children[char]
            if current_node.output:
                matches.append((i - len(current_node.output[0]) + 1, current_node.output[0]))
        
        return matches

# 示例用法
patterns = ["ab", "abc", "bc", "c"]
text = "abcdefg"
ac = AhoCorasick(patterns)
matches = ac.match(text)
for match in matches:
    print("Pattern '{}' found at index {}".format(match[1], match[0]))

以上代码实现了一个Aho-Corasick算法的类AhoCorasick,通过调用match方法可以在指定文本中查找多个模式串的出现位置。在示例中,模式串列表为["ab", "abc", "bc", "c"],文本为"abcdefg",输出结果为:

Pattern 'ab' found at index 0
Pattern 'bc' found at index 1
Pattern 'c' found at index 2

这表明在文本中分别找到了模式串"ab""bc""c",它们的起始位置分别为0、1和2。

相关内容

热门资讯

iwatch怎么连接安卓系统,... 你有没有想过,那款时尚又实用的iWatch,竟然只能和iPhone好上好?别急,今天就来给你揭秘,怎...
安卓系统怎么连不上carlif... 安卓系统无法连接CarLife的原因及解决方法随着智能手机的普及,CarLife这一车载互联功能为驾...
oppo手机安卓系统换成苹果系... OPPO手机安卓系统换成苹果系统:现实吗?如何操作?随着智能手机市场的不断发展,用户对于手机系统的需...
iphone系统与安卓系统更新... 最近是不是你也遇到了这样的烦恼?手机更新系统总是失败,急得你团团转。别急,今天就来给你揭秘为什么iP...
安卓系统上滑按键,便捷生活与高... 你有没有发现,现在手机屏幕越来越大,操作起来却越来越方便了呢?这都得归功于安卓系统上的那些神奇的上滑...
安卓平板改windows 系统... 你有没有想过,你的安卓平板电脑是不是也能变身成Windows系统的超级英雄呢?想象在同一个设备上,你...
安卓系统连接耳机模式,蓝牙、有... 亲爱的手机控们,你们有没有遇到过这种情况:手机突然变成了“耳机模式”,明明耳机没插,声音却只从耳机孔...
希沃系统怎么装安卓系统,解锁更... 亲爱的读者们,你是否也像我一样,对希沃一体机上的安卓系统充满了好奇呢?想象在教室里,你的希沃一体机不...
安装了Anaconda之后找不... 在安装Anaconda后,如果找不到Jupyter Notebook,可以尝试以下解决方法:检查环境...
安卓换鸿蒙系统会卡吗,体验流畅... 最近手机圈可是热闹非凡呢!不少安卓用户都在议论纷纷,说鸿蒙系统要来啦!那么,安卓手机换上鸿蒙系统后,...