Limour/llama-python-streamingllm

1def compute_lps_array(sublist):2    """3    计算模式串的最长前缀后缀匹配数组（LPS数组）4    """5    lps = [0] * len(sublist)6    j = 07    i = 18    while i < len(sublist):9        if sublist[i] == sublist[j]:10            j += 111            lps[i] = j12            i += 113        else:14            if j != 0:15                j = lps[j - 1]16            else:17                lps[i] = 018                i += 119    return lps20 21 22def kmp_search(main_list, sublist, _start=0, _end=None, lps=None):23    """24    使用KMP算法在列表上查找子串25    """26    if not sublist:27        return 028    if _end is None:29        _end = len(main_list)30    if lps is None:31        lps = compute_lps_array(sublist)32    i = _start  # 指向主串的索引33    j = 0  # 指向子串的索引34    while i < _end:35        if main_list[i] == sublist[j]:36            i += 137            j += 138            if j == len(sublist):39                return i - j40        else:41            if j != 0:42                j = lps[j - 1]43            else:44                i += 145    return -146 47 48if __name__ == '__main__':49    a = [1, 1, 3, 2, 3, 6, 7, 8, 3, 2, 3]50    b = [3, 2, 3]51    c = compute_lps_array(b)52    print(kmp_search(a, b, lps=c))53    print(kmp_search(a, b, 3, lps=c))54    print(kmp_search(a, b, 3, 10, lps=c))55    print(kmp_search(a, b, 9, lps=c))56