2、请实现使用KMP(Knuth-Morris-Pratt)算法在 text 中查找 pattern 的出现的位置。 例如口: text= "ababcabcacbab", pattern="abcac".

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，它通过预处理模式串，避免了不必要的回溯搜索，提高了查找效率。下面是使用Python实现KMP算法查找pattern在text中的位置：

首先，我们需要准备两个辅助函数。`compute_lps()`用于计算模式串的最长公共前后缀数组（Longest Proper Prefix which is also Suffix，简称LPS），`kmp_search()`则是实际的匹配过程。

def compute_lps(pattern):
    lps = [0] * len(pattern)
    j = 0
    
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                lps[i] = 0
                
    return lps

def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    lps = compute_lps(pattern)
    index = 0

    for i in range(text_len):
        if i < pattern_len and text[i] == pattern[index]:
            index += 1
        elif index > 0:
            index = lps[index - 1]
        else:
            continue
            
        # 找到匹配的位置
        if index == pattern_len:
            return i - pattern_len + 1
    return -1  # 如果没找到，返回-1

# 示例
text = "ababcabcacbab"
pattern = "abcac"
positions = [pos for pos in range(len(text) - len(pattern) + 1) if kmp_search(text, pattern)]
print(f"Pattern '{pattern}' found at positions {positions}")