Aho-Corasick algorithm to scan through a list of strings

Question

This is a follow-up to my previous question about finding min and max values of an iterable. Aho-Corasick algorithm was suggested to solve the problem. Below is my solution with the use of ahocorapy library.

Short re-cap of the problem:

You are given 2 arrays (genes and health), one of which have a 'gene' name, and the other - 'gene' weight (aka health). You then given a bunch of strings, each containing values m and n, which denote the start and end of the slice to be applied to the genes and health arrays, and the 'gene'-string, for which we need to determine healthiness. Then we need to return health-values for the most and the least healthy strings.

I think there might be something off with the code, but not sure what. It works quite fine for small testcases, giving more or less same timing as previous versions of the solution showed, but when it comes to large testcases, my PC basically hangs.

Example of a small testcase:

genes = ['a', 'b', 'c', 'aa', 'd', 'b']
health = [1, 2, 3, 4, 5, 6]
gene1 = "1 5 caaab" (result = 19 = max) 
gene2 = "0 4 xyz" (result = 0 = min) 
gene3 = "2 4 bcdybc" (result = 11)

Large testcase (2 lists 100K elements each; testcase 41K+ elements): txt in my dropbox (2,80 MB) (too large for pastebin)

So, I have 2 questions: 1) What is wrong with my code, how can I impore its performace 2) How do I apply the Aho-Corasick without turning to any non-standard library (because, most likely, it cannot be installed on HackerRank server)

def geneshealth(genes, health, testcase):
    from ahocorapy.keywordtree import KeywordTree
    import math

    min_weight = math.inf
    max_weight = -math.inf

    for case in testcase:
        #construct the keyword tree from appropriately sliced "genes" list
        kwtree = KeywordTree(case_insensitive=True)
        fl, ceil, g = case.split()
        for i in genes[int(fl):int(ceil)+1]:
            kwtree.add(i)
        kwtree.finalize()
        #search the testcase list for matches
        result = list(kwtree.search_all(g))

        hea = 0
        for gn, _ in result:
            for idx, val in enumerate(genes):
                if val == gn:
                    hea += health[idx]

        if hea < min_weight:
            min_weight = hea
        if hea > max_weight:
            max_weight = hea
    return(min_weight, max_weight)

Answer 1

This code is slow because:

1. It builds a new keyword tree for each test case. Just build it once, using all the genes.
2. It builds a list of all the matching keywords. KeywordTree.search_all() is a generator, just loop over it directly. And,
3. It loops over the list of genes to find the gene index, so that it can find the health.
   Instead, build a dict with the genes as keys and an (index, health) tuple for the value.

Something like this (untested):

import math
from collections import defaultdict
from ahocorapy.keywordtree import KeywordTree


def geneshealth(genes, health, testcases):

    # build the kwtree using all the genes 
    kwtree = KeywordTree(case_insensitive=True)
    for gene in genes:
        kwtree.add(gene)
    kwtree.finalize()

    # build a dict that maps a gene to a list of (index, health) tuples
    index_and_health = defaultdict(list)
    for gene, data in zip(genes, enumerate(health)):
        index_and_health[gene].append(data)

    min_dna_health = math.inf
    max_dna_health = -math.inf

    for case in testcases:
        start, end, dna = case.split()
        start = int(start)
        end = int(end)

        dna_health = 0

        # search the dna for any genes in the kwtree
        # note: we don't care where the gene is in the dna
        for gene, _ in kwtree.search_all(dna):

            for gene_index, gene_health in index_and_health[gene]:

                # only genes that are within the testcase limits
                # contribute dna_health
                if start <= gene_index <= end:
                    dna_health += gene_health

        # keep the min/max weight
        if dna_health < min_dna_health:
            min_dna_health = dna_health

        if dna_health > max_dna_health:
            max_dna_health = dna_health

    return(min_dna_health, max_dna_health)