当前位置：首页 > news >正文

高级字符串算法

news 2025/5/14 6:24:22

最长公共子串/子序列

最长公共子串

算法步骤

代码示例

复杂度分析

最长公共子序列

算法步骤

代码示例

复杂度分析

正则表达式匹配

正则表达式语法

代码示例

NFA与DFA在正则表达式匹配中的应用

NFA（非确定性有限自动机）

DFA（确定性有限自动机）

NFA与DFA的比较

字符串编辑距离（Levenshtein距离）

定义与计算

算法步骤

代码示例

应用场景

在高级字符串算法中，处理更复杂的字符串操作需求，如查找最长公共子串/子序列、正则表达式匹配，以及计算字符串的编辑距离。这些算法在自然语言处理、生物信息学、文本搜索等领域有广泛的应用。

最长公共子串/子序列

最长公共子串

最长公共子串（Longest Common Substring，LCS）是指两个字符串中长度最长的公共子串。通过动态规划，可以有效地找到最长公共子串。

算法步骤

创建一个二维数组 dp，其中 dp[i][j] 表示字符串 A[0:i] 和 B[0:j] 的最长公共后缀长度。
初始化 dp[0][j] 和 dp[i][0] 为0，因为任何字符串与空串的最长公共子串长度为0。
逐步填充 dp 表：如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。
遍历 dp 数组，记录最大值即为最长公共子串的长度。

代码示例

python语言：

def longest_common_substring(A, B):m, n = len(A), len(B)dp = [[0] * (n + 1) for _ in range(m + 1)]max_length = 0for i in range(1, m + 1):for j in range(1, n + 1):if A[i - 1] == B[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1max_length = max(max_length, dp[i][j])return max_length# 示例使用
A = "ABCXYZ"
B = "XYZABC"
print(longest_common_substring(A, B))  # 输出: 3

C语言：

#include <stdio.h>
#include <stdlib.h>int longestCommonSubstring(char *A, char *B) {int m = strlen(A);int n = strlen(B);int **dp = (int **)malloc((m + 1) * sizeof(int *));for (int i = 0; i <= m; i++) {dp[i] = (int *)calloc(n + 1, sizeof(int));}int max_length = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (A[i - 1] == B[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > max_length) {max_length = dp[i][j];}}}}for (int i = 0; i <= m; i++) {free(dp[i]);}free(dp);return max_length;
}int main() {char A[] = "ABCXYZ";char B[] = "XYZABC";int length = longestCommonSubstring(A, B);printf("%d\n", length);return 0;
}

复杂度分析

时间复杂度：O(n * m)，其中 n 和 m 分别是两个字符串的长度。
空间复杂度：O(n * m)，用于存储动态规划表。

最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指在不改变字符串顺序的前提下，两个字符串中长度最长的公共子序列。

算法步骤

创建一个二维数组 dp，其中 dp[i][j] 表示字符串 A[0:i] 和 B[0:j] 的最长公共子序列长度。
初始化 dp[0][j] 和 dp[i][0] 为0。
逐步填充 dp 表：如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
dp[m][n] 的值即为最长公共子序列的长度。

代码示例

def longest_common_subsequence(A, B):m, n = len(A), len(B)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if A[i - 1] == B[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]# 示例使用
A = "ABCBDAB"
B = "BDCAB"
print(longest_common_subsequence(A, B))  # 输出: 4

复杂度分析

时间复杂度：O(n * m)，其中 n 和 m 分别是两个字符串的长度。
空间复杂度：O(n * m)。

正则表达式匹配

正则表达式是一种用于描述字符串匹配模式的强大工具，广泛用于文本搜索、替换等操作中。Python的 re 模块提供了丰富的正则表达式操作函数，如 re.search()、re.match()、re.sub() 等。

正则表达式语法

.：匹配任意单个字符。
*：匹配前一个字符0次或多次。
+：匹配前一个字符1次或多次。
?：匹配前一个字符0次或1次。
[]：匹配括号内的任意字符。
^：匹配字符串的开始。
$：匹配字符串的结束。

代码示例

python语言：

import re# 检查字符串是否包含数字
pattern = r"\d+"
text = "There are 3 apples."
match = re.search(pattern, text)if match:print("Found a match:", match.group())  # 输出: Found a match: 3

C语言：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>bool hasDigits(const char *str) {for (int i = 0; str[i]!= '\0'; i++) {if (str[i] >= '0' && str[i] <= '9') {return true;}}return false;
}int main() {char text[] = "There are 3 apples.";if (hasDigits(text)) {printf("Found a match.\n");} else {printf("No match found.\n");}return 0;
}

NFA与DFA在正则表达式匹配中的应用

NFA（非确定性有限自动机）

NFA允许从多个状态同时出发匹配正则表达式。它能够灵活处理复杂的匹配模式，但匹配速度相对较慢。

DFA（确定性有限自动机）

DFA只有一个确定的状态转移路径，每次输入字符后只能有一个转移状态，匹配速度更快，但构造复杂，适合处理简单的正则表达式。

NFA与DFA的比较

灵活性：NFA更灵活，适合复杂的正则表达式匹配。
速度：DFA匹配速度更快，但在处理复杂模式时可能会导致状态爆炸。

字符串编辑距离（Levenshtein距离）

定义与计算

编辑距离（Edit Distance），也称Levenshtein距离，是指将一个字符串转换为另一个字符串所需的最少编辑操作次数。编辑操作包括插入、删除和替换。

算法步骤

初始化一个二维数组 dp，dp[i][j] 表示将 A[0:i] 转换为 B[0:j] 所需的最少操作次数。
填充初始值 dp[0][j] 和 dp[i][0]，表示空串与字符串的距离。
逐步填充 dp 表：如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1]；否则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

代码示例

python语言：


def edit_distance(A, B):m, n = len(A), len(B)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):dp[i][0] = ifor j in range(1, n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if A[i - 1] == B[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1return dp[m][n]# 示例使用
A = "kitten"
B = "sitting"
print(edit_distance(A, B))  # 输出: 3

C语言：

#include <stdio.h>
#include <stdlib.h>// 返回三个数中的最小值
int min(int a, int b, int c) {int min_ab = (a < b)? a : b;return (min_ab < c)? min_ab : c;
}// 计算编辑距离
int editDistance(char *A, char *B) {int m = strlen(A);int n = strlen(B);int **dp = (int **)malloc((m + 1) * sizeof(int *));for (int i = 0; i <= m; i++) {dp[i] = (int *)malloc((n + 1) * sizeof(int));}for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (A[i - 1] == B[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);}}}int distance = dp[m][n];for (int i = 0; i <= m; i++) {free(dp[i]);}free(dp);return distance;
}// 测试示例
int main() {char A[] = "kitten";char B[] = "sitting";int distance = editDistance(A, B);printf("%d\n", distance);return 0;
}