筛选字符串列表，忽略其他项的子字符串

Question

我如何过滤包含字符串和子字符串的列表以只返回最长的字符串。（如果列表中的任何项是另一项的子字符串，则只返回较长的字符串。）

我有这个功能。有没有更快的方法？在

def filterSublist(lst):
    uniq = lst
    for elem in lst:
        uniq = [x for x in uniq if (x == elem) or (x not in elem)]
    return uniq

lst = ["a", "abc", "b", "d", "xy", "xyz"]
print filterSublist(lst)

> ['abc', 'd', 'xyz']
> Function time: 0.000011

Answer 1

顺序有关系吗？如果没有

a = ["a", "abc", "b", "d", "xy", "xyz"]

a.sort(key=len, reverse=True)
n = len(a)

for i in range(n - 1):
    if a[i]:
        for j in range(i + 1, n):
            if a[j] in a[i]:
                a[j] = ''


print filter(len, a)  # ['abc', 'xyz', 'd']

效率不高，但很简单。在

Answer 2

简单的二次时间解决方案如下：

res = []
n = len(lst)
for i in xrange(n):
    if not any(i != j and lst[i] in lst[j] for j in xrange(n)):
        res.append(lst[i])

但我们可以做得更好：

让$是一个不出现在任何字符串中的字符，其值比所有实际字符的值都要低。在

让S是所有字符串的串联，中间是$。在您的示例中，S = a$abc$b$d$xy$xyz。在

您可以在线性时间内生成S的suffix array。您还可以使用我描述的一个更简单的O（nlog^2n）构造算法in another answer。在

现在，对于lst中的每个字符串，检查它是否只在后缀数组中出现一次。可以进行两次二进制搜索来查找子字符串的位置，它们在后缀数组中形成一个连续的范围。如果字符串出现多次，则将其删除。在

通过预先计算LCP信息，这也可以在线性时间内完成。在

示例O（n log^2 n）实现，改编自my suffix array answer：

^{pr2}$

然而，解释开销很可能导致这比O（n2）方法慢，除非S真的很大（大约10^5个字符或更多）。在

Answer 3

您可以用矩阵形式将问题构建为：

import numpy as np

lst = np.array(["a", "abc", "b", "d", "xy", "xyz"], object)
out = np.zeros((len(lst), len(lst)), dtype=int)
for i in range(len(lst)):
    for j in range(len(lst)):
        out[i,j] = lst[i] in lst[j]

从中可以得到out为：

^{pr2}$

然后，答案将是lst的索引，其中沿列的òut的和是1（字符串本身就是）：

lst[out.sum(axis=1)==1]
#array(['abc', 'd', 'xyz'], dtype=object)

---

编辑： 您可以通过以下方式更有效地完成：

from numpy.lib.stride_tricks import as_strided
from string import find

size = len(lst)
a = np.char.array(lst)
a2 = np.char.array(as_strided(a, shape=(size, size),
                                 strides=(a.strides[0], 0)))

out = find(a2, a)
out[out==0] = 1
out[out==-1] = 0
print a[out.sum(axis=0)==1]
# chararray(['abc', 'd', 'xyz'], dtype='|S3')

a[out.sum(axis=0)==1]