正向最大匹配算法代码

正向最大匹配算法通常用于字符串模式匹配，比如在文本搜索、编辑距离计算等场景。它从左到右遍历主串，尝试找到与模式串相匹配的最长部分。以下是使用Python实现的一个简单版本：

def max_matching(text, pattern):
    n = len(text)
    m = len(pattern)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 初始化边界条件
    for i in range(1, m + 1):
        dp[0][i] = 0
    for i in range(1, n + 1):
        dp[i][0] = int(i == 1)

    # 动态规划核心步骤
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text[i - 1] == pattern[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

# 示例
text = "ababc"
pattern = "baba"
print(max_matching(text, pattern))  # 输出结果为 3，因为 "baba" 在 "ababc" 中的最大匹配长度是 3

在这个代码中，`dp[i][j]` 存储了以 `text[i-1]` 结束并且在前 `j` 位匹配的最长子串长度。正向最大匹配的过程就是通过比较当前字符是否相等来更新这个值。