字符串旋转

将字符串前面若干个字符移到字符串的尾部， 例如abcdef，将前面三个字符进行旋转后就是defabc

核心思想: 三步反转，两字符串分为两个部分，各自反转，然后整体反转。例如上面这个例子:

abc → cba、def → fed，合并起来就是cbafed，最后整体反转defabc。

字符串包含

字符串匹配

KMP算法，核心思想就是匹配失败的时候，不重头重新匹配，而是有选择的跳过匹配失败的地方，从下一个地方开始匹配。例如: 字符串BADBARBARD、要匹配的模式: BARD，当匹配到R的时候失败了，没必要重头从A来匹配，直接从匹配失败的地方开始重新匹配。但如果字符串是BABABABCABC、模式是: ABABC，那么当匹配到C失败后，我们不能直接从当前位置开始，这样会漏掉ABABC。这是因为模式本身实际是有边界的。ABAB，这里AB就是边界。对于有边界的字符我们应从失败的地方回退几个字符，这几个字符肯定是能匹配的，因为这几个字符是边界，前后都一样，因此我只要从边界的下一个字符开始继续匹配就可以了。最后这个问题就转换成如何求模式本身的边界问题了。

def kmp_search(text, pattern):
    """KMP字符串搜索算法实现"""
    if not pattern:
        return 0  # 如果模式为空字符串，我们认为它在索引0处匹配

    # 计算部分匹配表
    lsp = compute_lsp_table(pattern)

    j = 0  # text的索引
    k = 0  # pattern的索引
    while j < len(text):
        if text[j] == pattern[k]:
            j += 1
            k += 1
            if k == len(pattern):
                return j - k  # 找到匹配
        elif k > 0:
            k = lsp[k - 1]  # 不匹配，进行跳转
        else:
            j += 1

    return -1  # 没有找到匹配

字符串前后缀

计算字符串的最长相同的前后缀表，类似KMP算法，找前后缀的过程就跟找pattern一样。

def compute_lsp_table(pattern):
    lsp = [0] * len(pattern)  # 初始化LSP表
    j = 0  # 前缀的长度
		
    for i in range(1, len(pattern)):
				// 如果下一个字符不相同，那么当前位置的前缀就是前一个字符的最大前缀值
        while j > 0 and pattern[i] != pattern[j]:
            j = lsp[j - 1]  # 不匹配，跳转到前一个LSP
				
				// i == j，前后缀找到相同字符了，继续找下一个字符，j + 1
        if pattern[i] == pattern[j]:
            j += 1
				
        lsp[i] = j  # 设置LSP表的当前位置

    return lsp