Find_BWT.py

def find(search_string, input_string, mismatches=0, bwt_data=None, s_array=None):
    
    results = []
     
    if len(search_string) == 0:
        return("Empty Query String")
    if bwt_data is None:
        bwt_data = generate_all(input_string, s_array=s_array)
    
    letters, bwt, lf_map, count, s_array = bwt_data
    
    if len(letters) == 0:
        return("Empty Search String")

    if not set(search_string) <= letters:
        return []

    length = len(bwt)
    

    class Fuzzy(object):
        def __init__(self, **kwargs):
            self.__dict__.update(kwargs)

    fuz = [Fuzzy(search_string=search_string, begin=0, end=len(bwt) - 1,
                        mismatches=mismatches)]

    while len(fuz) > 0:
        p = fuz.pop()
        search_string = p.search_string[:-1]
        last = p.search_string[-1]
        all_letters = [last] if p.mismatches == 0 else letters
        for letter in all_letters:
            begin, end = update(p.begin, p.end, letter, lf_map, count, length)
            if begin <= end:
                if len(search_string) == 0:
                    results.extend(s_array[begin : end + 1])
                else:
                    miss = p.mismatches
                    if letter != last:
                        miss = max(0, p.mismatches - 1)
                    fuz.append(Fuzzy(search_string=search_string, begin=begin,
                                            end=end, mismatches=miss))
    return sorted(set(results))