ahocorasick库的官方文档：https://pyahocorasick.readthedocs.io/en/latest/

Pyahocorasick是一个快速且节省内存的库，用于精确或模糊的多模式字符串搜索，这意味着您可以在输入文本中同时发现多个关键字符串。字符串“index”可以提前构建并保存(作为pickle)到磁盘，以便重新加载和以后重用。该库提供了一个ahocorasick Python模块，您可以将其用作普通的类似dict的Trie树，也可以将Trie树转换为自动机，以实现高效的Aho-Corasick搜索。

练习题：（这题的本意是让练人者自己实现Aho-Corasick搜索，怎奈自己的水平不行，理解不了这算法，只能用现成的库实现，做为记录。）

下面是程序的简单输入测试数据，根据这个测试数据，展开题目（因为题目太长了）。

输入：

6
a b c aa d b
1 2 3 4 5 6
3
1 5 caaab
0 4 xyz
2 4 bcdybc

输出：

0 19

n=6，这代表关键字genes有6个。

genes=[‘a’, ‘b’, ‘c’, ‘aa’, ‘d’, ‘b’]，这是关键字

health=[1, 2, 3, 4, 5, 6]，这是值

s=3，代表下面要进行3次关键字的搜索

[1, 5, ‘caaab’]，first=1，last=5，d=’caaab’，first代表搜索关键字的开始位置（包含该位置，位置从0开始），last代表搜索关键字的结束位置（包含该位置，位置从0开始），d代表搜索字符串

[0,4, ‘xyz]，同上

[2, 4, ‘bcdybc’]，同上

关键字和值是对应的（可以把其看成是字典，但是要注意其中是有重复的关键字，但是拥有不同的值），关键字在first和last的范围内，查找d中出现的次数，并计算关键字对应的值的总和。

因此’caaab’的总合是3+4+4+2+6=19，其中的’aaa’要分解成’aaa’和’aaa‘，所以是两个4。因为first的位置是1,所以位置为0的关键字’a’就被跳过了。同时因为b有两个值，一个是2，另一个是6，而取值范围还包含了这两个值的位置，所以这两个值都要计算。

而’xyz’没有对应的关键字，因此总合是0

而’bcdybc’中只有部分关键字存在，所以总合是3+5+3=11

题目：在s次的搜索中找出最小值和最大值。

调用ahocorasick库的程序：

import ahocorasick
def func2():
    trie=ahocorasick.Automaton()

    n = int(input().strip())

    genes = input().rstrip().split()

    health = list(map(int, input().rstrip().split()))

    s = int(input().strip())
    i=0

    #向trie中添加关键字，关键字是列表的原因是要输入重复的关键字，而且ahocorasick的实例中输入重复的关键字时，会将旧的值覆盖。add_word(关键字,值）
    for k,v in zip(genes,health):
        if k in trie.keys():
            trie.get(k).append((i,v,))
        else:
            trie.add_word(k,[(i,v,)])
        i = i + 1

    # 使trie变成Aho-Corasick自动机，让trie可以进行 Aho-Corasick搜索
    trie.make_automaton()
    result = []
    for s_itr in range(s):
        first_multiple_input = input().rstrip().split()

        first = int(first_multiple_input[0])

        last = int(first_multiple_input[1])

        d = first_multiple_input[2]
        count_genes=0
        #在trie中进行 Aho-Corasick搜索，d就是被搜索的字符串，trie.iter(d)可以返回所有找到的关键字，其返回值是（位置，值）这样的元祖。位置是关键字在d中的位置，值就是关键字对应的值。
        for i in trie.iter(d):
            for j in i[1]:
                if first<=j[0]<=last:
                    count_genes+=j[1]
        result.append(count_genes)
    print(f'{min(result)} {max(result)}')

test中有三个测试数据，结果如下：
    result={
        'test_data0.txt':'0 19',
        'test_data1.txt':'11674463 11674463',
        'test_data2.txt':'15806635 20688978289',
    }

如果用暴力的比对方式的话，后两个测试数据运行时间可高达十几分钟，使用 Aho-Corasick搜索，1分钟内就可以得到结果。

这篇算法的论文可以让我们更好的理解Aho-Corasick搜索，但是我放弃了。