blocks|key|115727|text|一个简单的二次时间解是这样的：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|115728|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])|code-block|syntax|javascript|115729|但我们可以做得更好：|115730|假设$是一个不会出现在任何字符串中的字符，并且其值小于所有实际字符。|offset|length|style|CODE|115731|假设S是所有字符串的串联，$在其间。在您的示例中，S+=+a$abc$b$d$xy$xyz。|115732|可以在线性时间内构建S的suffix+array。您还可以使用一个简单得多的O(nlog%5E2n)构造算法，正如我在in+another+answer中描述的那样。|115733|现在，对于lst中的每个字符串，检查它是否只在后缀数组中出现一次。您可以执行两个二进制搜索来查找子字符串的位置，它们在后缀数组中形成一个连续的范围。如果字符串多次出现，则将其删除。|115734|通过预先计算LCP信息，这也可以在线性时间内完成。|115735|O(nlog%5E2n)实现示例，改编自my+suffix+array+answer|115736|def+findFirst(lo,+hi,+pred):
++"""+Find+the+first+i+in+range(lo,+hi)+with+pred(i)+==+True.
++Requires+pred+to+be+a+monotone.+If+there+is+no+such+i,+return+hi.+"""
++while+lo+<+hi:
++++mid+=+(lo+%2B+hi)+//+2
++++if+pred(mid):+hi+=+mid;
++++else:+lo+=+mid+%2B+1
++return+lo

#+uses+the+algorithm+described+in+https://stackoverflow.com/a/21342145/916657
class+SuffixArray(object):
++def+__init__(self,+s):
++++"""+build+the+suffix+array+of+s+in+O(n+log%5E2+n)+where+n+=+len(s).+"""
++++n+=+len(s)
++++log2+=+0
++++while+(1<<log2)+<+n:
++++++log2+%2B=+1
++++rank+=+[[0]*n+for+_+in+xrange(log2)]
++++for+i+in+xrange(n):
++++++rank[0][i]+=+s[i]
++++L+=+[0]*n
++++for+step+in+xrange(1,+log2):
++++++length+=+1+<<+step
++++++for+i+in+xrange(n):
++++++++L[i]+=+(rank[step+-+1][i],
++++++++++++++++rank[step+-+1][i+%2B+length+//+2]+if+i+%2B+length+//+2+<+n+else+-1,
++++++++++++++++i)
++++++L.sort()
++++++for+i+in+xrange(n):
++++++++rank[step][L[i][2]]+=+\
++++++++++rank[step][L[i+-+1][2]]+if+i+>+0+and+L[i][:2]+==+L[i-1][:2]+else+i
++++self.log2+=+log2
++++self.rank+=+rank
++++self.sa+=+[l[2]+for+l+in+L]
++++self.s+=+s
++++self.rev+=+[0]*n
++++for+i,+j+in+enumerate(self.sa):
++++++self.rev[j]+=+i

++def+lcp(self,+x,+y):
++++"""+compute+the+longest+common+prefix+of+s[x:]+and+s[y:]+in+O(log+n).+"""
++++n+=+len(self.s)
++++if+x+==+y:
++++++return+n+-+x
++++ret+=+0
++++for+k+in+xrange(self.log2+-+1,+-1,+-1):
++++++if+x+>=+n+or+y+>=+n:
++++++++break
++++++if+self.rank[k][x]+==+self.rank[k][y]:
++++++++x+%2B=+1<<k
++++++++y+%2B=+1<<k
++++++++ret+%2B=+1<<k
++++return+ret

++def+compareSubstrings(self,+x,+lx,+y,+ly):
++++"""+compare+substrings+s[x:x%2Blx]+and+s[y:y%2Byl]+in+O(log+n).+"""
++++l+=+min((self.lcp(x,+y),+lx,+ly))
++++if+l+==+lx+==+ly:+return+0
++++if+l+==+lx:+return+-1
++++if+l+==+ly:+return+1
++++return+cmp(self.s[x+%2B+l],+self.s[y+%2B+l])

++def+count(self,+x,+l):
++++"""+count+occurences+of+substring+s[x:x%2Bl]+in+O(log+n).+"""
++++n+=+len(self.s)
++++cs+=+self.compareSubstrings
++++lo+=+findFirst(0,+n,+lambda+i:+cs(self.sa[i],+min(l,+n+-+self.sa[i]),+x,+l)+>=+0)
++++hi+=+findFirst(0,+n,+lambda+i:+cs(self.sa[i],+min(l,+n+-+self.sa[i]),+x,+l)+>+0)
++++return+hi+-+lo

++def+debug(self):
++++"""+print+the+suffix+array+for+debugging+purposes.+"""
++++for+i,+j+in+enumerate(self.sa):
++++++print+str(i).ljust(4),+self.s[j:],+self.lcp(self.sa[i],+self.sa[i-1])+if+i+>0+else+"n/a"

def+filterSublist(lst):
++splitter+=+"\x00"
++s+=+splitter.join(lst)+%2B+splitter
++sa+=+SuffixArray(s)
++res+=+[]
++offset+=+0
++for+x+in+lst:
++++if+sa.count(offset,+len(x))+==+1:
++++++res.append(x)
++++offset+%2B=+len(x)+%2B+1
++return+res|115737|但是，解释开销可能会导致这种方法比O(n%5E2)方法更慢，除非S非常大(大约10%5E5个字符或更多)。|115738|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Suffix_array|1|https://stackoverflow.com/questions/21220150/rank-the-suffix-of-a-list|2|https://stackoverflow.com/a/21342145/916657^0|0|0|0|2|1|0|2|1|D|1|P|K|0|A|1|C|C|0|1L|H|1|0|5|3|0|0|I|M|2|0|0|U|1|0^^$0|@$1|2|3|4|5|6|7|1E|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1F|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1G|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|1H|8|@$K|1I|L|1J|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|1K|8|@$K|1L|L|1M|M|N]|$K|1N|L|1O|M|N]|$K|1P|L|1Q|M|N]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1R|8|@$K|1S|L|1T|M|N]]|9|@$K|1U|L|1V|1|1W]|$K|1X|L|1Y|1|1Z]]|A|$]]|$1|S|3|T|5|6|7|20|8|@$K|21|L|22|M|N]]|9|@]|A|$]]|$1|U|3|V|5|6|7|23|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|24|8|@]|9|@$K|25|L|26|1|27]]|A|$]]|$1|Y|3|Z|5|D|7|28|8|@]|9|@]|A|$E|F]]|$1|10|3|11|5|6|7|29|8|@$K|2A|L|2B|M|N]]|9|@]|A|$]]|$1|12|3|-4|5|6|7|2C|8|@]|9|@]|A|$]]]|13|$14|$5|15|16|17|A|$18|19]]|1A|$5|15|16|17|A|$18|1B]]|1C|$5|15|16|17|A|$18|1D]]]]

A simple quadratic time solution would be this:

<pre><code>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])
</code></pre>

But we can do much better:

Let <code>$</code> be a character that does not appear in any of your strings and has a lower value than all your actual characters.

Let <code>S</code> be the concatenation of all your strings, with <code>$</code> in between. In your example, <code>S = a$abc$b$d$xy$xyz</code>.

You can build the <a href="http://en.wikipedia.org/wiki/Suffix_array" rel="nofollow noreferrer">suffix array</a> of <code>S</code> in linear time. You can also use a much simpler O(n log^2 n) construction algorithm that I described <a href="https://stackoverflow.com/questions/21220150/rank-the-suffix-of-a-list">in another answer</a>.

Now for every string in <code>lst</code>, check if it occurs in the suffix array exactly once. You can do two binary searches to find the locations of the substring, they form a contiguous range in the suffix array. If the string occurs more than once, you remove it.

With LCP information precomputed, this can be done in linear time as well.

Example O(n log^2 n) implementation, adapted from <a href="https://stackoverflow.com/a/21342145/916657">my suffix array answer</a>:

<pre><code>def findFirst(lo, hi, pred):
 """ Find the first i in range(lo, hi) with pred(i) == True.
 Requires pred to be a monotone. If there is no such i, return hi. """
 while lo &lt; hi:
 mid = (lo + hi) // 2
 if pred(mid): hi = mid;
 else: lo = mid + 1
 return lo

# uses the algorithm described in https://stackoverflow.com/a/21342145/916657
class SuffixArray(object):
 def __init__(self, s):
 """ build the suffix array of s in O(n log^2 n) where n = len(s). """
 n = len(s)
 log2 = 0
 while (1&lt;&lt;log2) &lt; n:
 log2 += 1
 rank = [[0]*n for _ in xrange(log2)]
 for i in xrange(n):
 rank[0][i] = s[i]
 L = [0]*n
 for step in xrange(1, log2):
 length = 1 &lt;&lt; step
 for i in xrange(n):
 L[i] = (rank[step - 1][i],
 rank[step - 1][i + length // 2] if i + length // 2 &lt; n else -1,
 i)
 L.sort()
 for i in xrange(n):
 rank[step][L[i][2]] = \
 rank[step][L[i - 1][2]] if i &gt; 0 and L[i][:2] == L[i-1][:2] else i
 self.log2 = log2
 self.rank = rank
 self.sa = [l[2] for l in L]
 self.s = s
 self.rev = [0]*n
 for i, j in enumerate(self.sa):
 self.rev[j] = i

 def lcp(self, x, y):
 """ compute the longest common prefix of s[x:] and s[y:] in O(log n). """
 n = len(self.s)
 if x == y:
 return n - x
 ret = 0
 for k in xrange(self.log2 - 1, -1, -1):
 if x &gt;= n or y &gt;= n:
 break
 if self.rank[k][x] == self.rank[k][y]:
 x += 1&lt;&lt;k
 y += 1&lt;&lt;k
 ret += 1&lt;&lt;k
 return ret

 def compareSubstrings(self, x, lx, y, ly):
 """ compare substrings s[x:x+lx] and s[y:y+yl] in O(log n). """
 l = min((self.lcp(x, y), lx, ly))
 if l == lx == ly: return 0
 if l == lx: return -1
 if l == ly: return 1
 return cmp(self.s[x + l], self.s[y + l])

 def count(self, x, l):
 """ count occurences of substring s[x:x+l] in O(log n). """
 n = len(self.s)
 cs = self.compareSubstrings
 lo = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) &gt;= 0)
 hi = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) &gt; 0)
 return hi - lo

 def debug(self):
 """ print the suffix array for debugging purposes. """
 for i, j in enumerate(self.sa):
 print str(i).ljust(4), self.s[j:], self.lcp(self.sa[i], self.sa[i-1]) if i &gt;0 else "n/a"

def filterSublist(lst):
 splitter = "\x00"
 s = splitter.join(lst) + splitter
 sa = SuffixArray(s)
 res = []
 offset = 0
 for x in lst:
 if sa.count(offset, len(x)) == 1:
 res.append(x)
 offset += len(x) + 1
 return res
</code></pre>

However, the interpretation overhead likely causes this to be slower than the O(n^2) approaches unless <code>S</code> is really large (in the order of 10^5 characters or more).

blocks|key|115766|text|顺序重要吗？如果不是，|type|unstyled|depth|inlineStyleRanges|entityRanges|data|115767|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+%2B+1,+n):
++++++++++++if+a[j]+in+a[i]:
++++++++++++++++a[j]+=+''


print+filter(len,+a)++#+['abc',+'xyz',+'d']|code-block|syntax|javascript|115768|效率不是很高，但很简单。|115769|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Does the order matter? If not, 

<pre><code>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']
</code></pre>

Not very efficient, but simple.

How can I filter through a list which containing strings and substrings to return only the longest strings. (If any item in the list is a substring of another, return only the longer string.)

I have this function. Is there a faster way?

<pre><code>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)

&gt; ['abc', 'd', 'xyz']
&gt; Function time: 0.000011
</code></pre>

Filter list of strings, ignoring substrings of other items

如何过滤包含字符串和子字符串的列表，以便只返回最长的字符串。(如果列表中的任何项是另一项的子字符串，则仅返回较长的字符串。)我有这个功能。有没有更快的方法？def filterSublist(lst):    uniq = lst    for elem in lst:        uniq = [x for x i...

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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