python 中字符串的最大公约数

发布于 2024-12-11 22:26:50 字数 268 浏览 1 评论 0 原文

我想要一个 python 函数，给定列表

mystrings = ['abcde', 'abcdf', 'abcef', 'abcnn']

返回字符串“abc”，即列表中所有元素包含的最长的一段。我有一个解决方案，只需循环遍历 mystring[0] 的切片，并将其与其余部分进行比较，并在找到第一个不匹配的子字符串时跳出循环。然而，我怀疑一定有一种更高效、更优雅、更Python 的方式来做到这一点。

有人可以指出如何正确执行此操作吗？

原文

I would like to have a python function that given the list

mystrings = ['abcde', 'abcdf', 'abcef', 'abcnn']

returns the string 'abc', i.e., the longest piece contained by all the elements in the list. I have a solution which just loops through the slices of mystring[0], and compares it to the rest, and breaks out of the loop, whenever the first unmatching substring is found. However, I suspect that there must be a more efficient, elegant, and pythonic way of doing this.

Could someone point out how to do this properly?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

江心雾 2024-12-18 22:26:50

按照您描述的方式，您希望在起点处使用最大的子字符串：

>>> os.path.commonprefix(['abcde', 'abcdf', 'abcef', 'abcnn'])
'abc'

The way you described, you want the biggest substring at the starting point:

>>> os.path.commonprefix(['abcde', 'abcdf', 'abcef', 'abcnn'])
'abc'

回复收藏 0 原文

甜点 2024-12-18 22:26:50

一旦您意识到“最长公共子串”是您所描述的问题，就很容易找到您想要的内容：

例如，来自维基教科书：

def LongestCommonSubstring(S1, S2):
    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
    longest, x_longest = 0, 0
    for x in xrange(1,1+len(S1)):
        for y in xrange(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]

Once you realize that "Longest Common Substring" is the problem you're describing, it's easy to find what you want:

eg, from Wikibooks:

def LongestCommonSubstring(S1, S2):
    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
    longest, x_longest = 0, 0
    for x in xrange(1,1+len(S1)):
        for y in xrange(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]

回复收藏 0 原文

~没有更多了~