Python递归实现字符串匹配算法

字符串匹配算法，就是在一个长字符串中，查找是否存在一个给定的短字符串。经典算法包括暴力算法、KMP算法和Boyer-Moore算法。其中，暴力算法的时间复杂度是O(m*n)，KMP算法和Boyer-Moore算法都是O(m+n)。本文将介绍Python递归实现字符串匹配算法。
递归实现字符串匹配算法的核心思想是：每次比较长字符串和短字符串的第一个字符是否相同，如果相同，则递归调用自身，比较长字符串和短字符串去掉第一个字符后的部分是否相同；如果不相同，则直接返回False。递归的边界条件是：短字符串为空，返回True；长字符串为空，返回False。
下面是Python递归实现字符串匹配算法的代码：

def match(long_str, short_str):
    if len(short_str) == 0:
        return True
    elif len(long_str) == 0:
        return False
    elif long_str[0] == short_str[0]:
        return match(long_str[1:], short_str[1:])
    else:
        return False
long_str = "pidancode.com"
short_str = "code"
print(match(long_str, short_str))
long_str = "皮蛋编程"
short_str = "编"
print(match(long_str, short_str))

首先定义了一个match函数，用于匹配长字符串long_str和短字符串short_str。接着判断短字符串是否为空，如果为空，说明短字符串已经匹配完毕，返回True；如果长字符串为空，说明已经匹配到长字符串的结尾，返回False。然后比较长字符串和短字符串的第一个字符是否相同，如果相同，则递归调用自身，比较长字符串和短字符串去掉第一个字符后的部分是否相同；如果不相同，则直接返回False。最后，可以用一些测试用例来检验代码是否正确。在上面的代码中，使用了两个测试用例，第一个测试用例匹配成功，第二个测试用例匹配失败。
递归实现字符串匹配算法比较简单，但是效率较低，优化的思路是采用非递归的方式，比如KMP算法和Boyer-Moore算法，以达到更高的效率。