博客

Python最长公共子串算法实例

  • Post category:Python

下面是详细讲解“Python最长公共子串算法实例”的完整攻略，包括算法原理、Python实现和两个示例说明。

算法原理

最长公共子串算法是一种用于查找两个字符串中最长公共子串的算法。其主要思想是将两个字符串分别以行和列的形式排列，然后查找它们的交叉点，找到最长的交叉点序列，即为最长公共子串。最长公共子串算法的实现过程如下：

  1. 构建一个二维数组，用于存储两个字符串中每个字符的匹配情况。
  2. 遍历二维数组，查找最长的连续匹配子串。
  3. 返回最长的连续匹配子串。

Python实现

以下是Python实现最长公共子串算法的示例代码：

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

s1 = "abcdefg"
s2 = "defghijk"
print(longest_common_substring(s1, s2))

上述代码中使用Python实现了最长公共子串算法。首先定义一个函数longest_common_substring，该函数接受两个字符串s1和s2作为参数。然后构建一个二维数组m，用于存储两个字符串中每个字符的匹配情况。接着遍历二维数组，查找最长的连续匹配子串。最后返回最长的连续匹配子串。

示例说明

以下两个示例，说明如何使用上述代码进行最长公共子串查找。

示例1

使用最长公共子串算法查找两个字符串的最长公共子串。

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] >:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

s1 = "abcdefg"
s2 = "defghijk"
print(longest_common_substring(s1, s2))

运行上述代码，输出结果为”def”，即为两个字符串的最长公共子串。

上述代码中，使用最长公共子串算法查找两个字符串的最长公共子串。首先定义一个函数longest_common_substring，该函数接受两个字符串s1和s2作为参数。然后构建一个二维数组m，用于存储两个字符串中每个字符的匹配情况。接着遍历二维数组，查找最长的连续匹配子串。最后返回最长的连续匹配子串。

示例2

使用最长公共子串算法查找多个字符串的最长公共子串。

def longest_common_substring(*args):
    s = min(args, key=len)
    for i, c in enumerate(s):
        if not all(c == arg[i] for arg in args):
            return s[:i]
    return s

s1 = "abcdefg"
s2 = "defghijk"
s3 = "ghijklmn"
print(longest_common_substring(s1, s2, s3))

运行上述代码，输出结果为”g”，即为多个字符串的最长公共子串。

上述代码中，使用最长公共子串算法查找个字符串的最长公共子串。首先定义一个函数longest_common_substring，该函数接受多个字符串作为参数。然后使用min函数找到最短的字符串s。接遍历最短的字符串s，查找最长的连续匹配子串。最后返回最长的连续匹配子串。

结语

本文介绍了如何使用Python实现最长公共子串算法进行字符串匹配，包括算法原理、Python实现和两个示例说明。最长公共子串算法是一种用于查找两个字符串中最长公共子串的算法，其主要思想是将两个字符串分别以行和列的形式排列，然后查找它们的交叉点，找到最长的交叉点序列，即为最长公共子串。在实现中，需要注意选择适当的参数，并根据具体情况调整。

Tags: ,