首页 > 编程语言 >高级字符串算法

高级字符串算法

时间：2024-09-01 14:23:10浏览次数：12  
标签：匹配 示例 int 高级 算法 字符串 range dp

目录

最长公共子串/子序列

最长公共子串

算法步骤

代码示例

复杂度分析

最长公共子序列

算法步骤

代码示例

复杂度分析

正则表达式匹配

正则表达式语法

代码示例

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

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

DFA（确定性有限自动机）

NFA与DFA的比较

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

定义与计算

算法步骤

代码示例

应用场景

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

最长公共子串/子序列

最长公共子串

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

算法步骤

  1. 创建一个二维数组 dp，其中 dp[i][j] 表示字符串 A[0:i] 和 B[0:j] 的最长公共后缀长度。
  2. 初始化 dp[0][j] 和 dp[i][0] 为0，因为任何字符串与空串的最长公共子串长度为0。
  3. 逐步填充 dp 表：如果 A[i-1] == B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。
  4. 遍历 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 = 0

    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] + 1
                max_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）是指在不改变字符串顺序的前提下，两个字符串中长度最长的公共子序列。

算法步骤

  1. 创建一个二维数组 dp，其中 dp[i][j] 表示字符串 A[0:i] 和 B[0:j] 的最长公共子序列长度。
  2. 初始化 dp[0][j] 和 dp[i][0] 为0。
  3. 逐步填充 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])。
  4. 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] + 1
            else:
                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距离，是指将一个字符串转换为另一个字符串所需的最少编辑操作次数。编辑操作包括插入、删除和替换。

算法步骤

  1. 初始化一个二维数组 dp，dp[i][j] 表示将 A[0:i] 转换为 B[0:j] 所需的最少操作次数。
  2. 填充初始值 dp[0][j] 和 dp[i][0]，表示空串与字符串的距离。
  3. 逐步填充 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] = i
    for j in range(1, n + 1):
        dp[0][j] = j

    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]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    return 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;
}

应用场景

  • 拼写检查：自动校正文本中的拼写错误。
  • DNA序列比较：在生物信息学中，计算两个DNA序列之间的相似性。

标签：匹配,示例,int,高级,算法,字符串,range,dp
From： https://blog.csdn.net/LS_Ai/article/details/141748863

相关文章

  • 基于感知哈希算法的以图搜图系统的设计
    摘 要随着数字媒体和计算机网络的迅猛发展，互联网上在线图像的飞速增长，用户对图形图像的搜索需求日益提高，一种“以图搜图”的新型搜索模式应运而生。“以图搜图”是以用户提供的图形图像图片等为视觉特征基础，为用户提供互联网上相关图形图像资料检索服务，这是一种专业的搜索引......
  • JAVA高级编程之集合框架和泛型（超详细）
    Java集合框架包含的内容Java集合框架提供了一套性能优良、使用方便的接口和类，它们位于java.util包中Collection接口存储一组不唯一，无序的对象List接口存储一组不唯一，有序（插入顺序）的对象Set接口存储一组唯一，无序的对象Map接口存储一组键值对象，提供key到value的映......
  • 白骑士的CSS高级篇之CSS Grid布局进阶 4.1.2 网格模板与区域
            CSSGrid布局是CSS中强大的布局系统之一，它提供了更灵活和更高效的方式来创建复杂的网页布局。通过Grid布局，你可以将网页划分为多个网格区域，并在这些区域中放置内容，这使得布局更加直观和易于维护。本文将深入探讨Grid布局中的网格模板和区域的概念，帮助你掌握如......
  • [转]高斯-牛顿算法
    Gauss-Newton算法是解决非线性最优问题的常见算法之一，最近研读开源项目代码，又碰到了，索性深入看下。本次讲解内容如下： 基本数学名词识记牛顿法推导、算法步骤、计算实例高斯牛顿法推导(如何从牛顿法派生)、算法步骤、编程实例高斯牛顿法优劣总结  一、基本概念定义1.......
  • 电商导购平台的推荐算法与大数据应用
    电商导购平台的推荐算法与大数据应用大家好，我是微赚淘客返利系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！电商导购平台的核心竞争力之一就是为用户提供个性化的购物体验，而推荐算法和大数据技术的应用是实现这一目标的关键。本文将探讨电商导购平台中推荐算法的设计和实现，以......
  • 对偶单纯形法算法精要
    单纯形法是线性规划中最经典且广泛应用的求解方法，通过在可行解的边界上移动，逐步逼近最优解。它从一个初始基本可行解开始，不断优化目标函数值，直到找到最优解。对偶单纯形法则是单纯形法的一种变形，尤其适用于特定类型的线性规划问题。不同于标准的单纯形法，对偶单纯形法从一个对偶可......
  • 「代码随想录算法训练营」第五十一天 | 图论 part9
    目录Bellman_ford算法模拟过程题目：94.城市间货物运输IBellman_ford队列优化算法（又名SPFA）模拟过程题目：94.城市间货物运输IBellman_ford算法之判断负权回路题目：95.城市间货物运输IIBellman_ford算法之单源有限最短路题目：96.城市间货物运输IIIBellman_ford算法Bellman_ford算法......
  • 【GRNN-RBFNN-ILC算法】【轨迹跟踪】基于神经网络的迭代学习控制用于未知SISO非线性系
     ......
  • 【GRNN-RBFNN-ILC算法】【轨迹跟踪】基于神经网络的迭代学习控制用于未知SISO非线性系
     ......
  • 基于多目标灰狼优化算法的环境经济调度研究【IEEE30节点】（Matlab实现）
     ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99