python - 检查字符串是否在字符串中

Question

我有一个包含许多字符串的巨大列表，例如:

['xxxx','xx','xy','yy','x',......]

现在我正在寻找一种有效的方法来删除另一个字符串中存在的所有字符串。例如 'xx' 'x' 适合 'xxxx'。

由于数据集很大，我想知道除了这个之外是否有一种有效的方法

如果 a 在 b 中:

完整代码:可能有一些优化部分:

for x in range(len(taxlistcomplete)):
if delete == True:
    x = x - 1
    delete = False
for y in range(len(taxlistcomplete)):
    if taxlistcomplete[x] in taxlistcomplete[y]:
        if x != y:
            print x,y
            print taxlistcomplete[x]
            del taxlistcomplete[x]
            delete = True
            break
    print x, len(taxlistcomplete)

代码的更新版本:

for x in enumerate(taxlistcomplete):
if delete == True:
    #If element is removed, I need to step 1 back and continue looping.....
    delete = False
for y in enumerate(taxlistcomplete):
    if x[1] in y[1]:
        if x[1] != y[1]:
            print x[1],y[1]
            print taxlistcomplete[x]

            del taxlistcomplete[x[0]]
            delete = True
            break
print x, len(taxlistcomplete)

现在使用枚举实现，现在我想知道这是否更有效以及如何实现删除步骤，这样我也可以减少搜索。

只是一个简短的想法...

基本上是我想看到的...

如果元素与列表中的任何其他元素不匹配，则将此元素写入文件。因此，如果 'xxxxx' 不在 'xx'、'xy'、'wfirfj' 等中...打印/保存

一个新的简单版本，因为我认为我无法进一步优化它......

print 'comparison'

file = open('output.txt','a')

for x in enumerate(taxlistcomplete):
    delete = False
    for y in enumerate(taxlistcomplete):
        if x[1] in y[1]:
            if x[1] != y[1]:
                taxlistcomplete[x[0]] = ''
                delete = True
                break
    if delete == False:
        file.write(str(x))

Answer 1

x in <string>速度很快，但是根据列表中的所有其他字符串检查每个字符串将花费 O(n^2) 时间。无需通过优化比较来缩短几个周期，您可以通过使用不同的数据结构实现巨大的节省，这样您就可以在一次查找中检查每个字符串:对于两千个字符串，这是两千次检查而不是四百万次。

有一种称为“前缀树”(或 trie)的数据结构，可以让您非常快速地检查一个字符串是否是您之前见过的某个字符串的前缀。去谷歌上查询。由于您还对出现在另一个字符串 x 的中间 的字符串感兴趣, 索引形式为 x, x[1:], x[2:], x[3:], 的所有子字符串等等(所以:只有 n 长度为 n 的字符串的子串)。也就是说，您索引从位置 0、1、2 等开始并继续到字符串末尾的子字符串。这样您就可以检查新字符串是否是索引中某些内容的初始部分。

然后您可以像这样在 O(n) 时间内解决您的问题:

1. 按长度递减的顺序排列字符串。这确保没有字符串可以是您尚未看到的内容的子字符串。由于您只关心长度，因此您可以在 O(n) 时间内进行桶排序。

2. 从一个空的前缀树开始，循环遍历您的有序字符串列表。对于每个字符串 x ，使用你的前缀树来检查它是否是你之前见过的字符串的子串。如果不是，请添加其子字符串 x, x[1:], x[2:]等等到前缀树。

在一个长列表的中间删除是非常昂贵的，所以如果您将要保留的字符串收集到一个新列表中(实际字符串不会被复制，只是引用)，您将获得进一步的加速。完成后，删除原始列表和前缀树。

如果这对您来说太复杂，至少不要将所有内容与所有内容进行比较。按大小对字符串进行排序(按降序排列)，并且只检查每个字符串与之前的字符串。这将使您毫不费力地获得 50% 的加速。并制作一个新列表(或立即写入文件)而不是就地删除。