设计并实现求子串的算法

设计一个求子串的算法通常可以使用滑动窗口或者KMP（Knuth-Morris-Pratt）算法等方法。这里简单介绍一下这两种常见的方法：

1. **滑动窗口**:
- 简单来说，将字符串分为两部分：固定大小的窗口和剩余的部分。窗口从左向右移动，每次移动一位，同时更新窗口内的最长公共前缀和后缀。
- 当窗口遇到新的字符，如果它与已知的最长公共后缀不符，则需要缩小窗口。直到找到匹配或者窗口移到了字符串的末尾。

def find_substring(s, sub):
    n = len(s)
    m = len(sub)
    max_len = 0
    start = 0

    for i in range(n - m + 1):
        if s[i:i+m] == sub:
            max_len = m
            start = i
        else:
            # 如果当前窗口与sub不符，尝试缩短窗口长度
            while i > start and s[i] != s[start]:
                start += 1
    return max_len, start

2. **KMP（Knuth-Morris-Pratt）算法**:
- 这是一种更高效的方法，通过构建一个失配表（也叫失败函数），记录前缀到当前位置的最长匹配子串长度。当遇到不匹配时，不是直接缩小窗口，而是利用失配表快速跳过已经匹配过的字符。

- KMP 算法适用于有大量重复的子串查找场景。

以下是KMP算法的一个简化版本的Python实现：

def build_lps(pattern):
    lps = [0]
    length = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[length]:
            length += 1
            lps.append(length)
        else:
            if length != 0:
                length = lps[length-1]
            else:
                lps.append(0)
    return lps

def kmp_search(text, pattern):
    text_len, pattern_len = len(text), len(pattern)
    lps = build_lps(pattern)
    i, j = 0, 0
    while i < text_len:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        elif j != 0:
            j = lps[j-1]
        else:
            i += 1
    if j == pattern_len:
        return i - j
    return -1