让我们一步一步地来。您需要处理以下几个子任务:
- 识别长度为4或更长的所有子字符串。
- 计算这些子字符串的出现次数。
- 过滤掉出现2次或更多次的所有子字符串。
实际上,您可以将所有任务放在几个语句中。为了易于理解,最好逐个任务来处理。
以下示例都使用
mystring = "abcdthisisatextwithsampletextforasampleabcd"
min_length = 4
1. 给定长度的子字符串
您可以通过切片轻松获得子字符串 - 例如,mystring[4:4+6]
将给您长度为6的从位置4开始的子字符串:'thisis'
。更一般地,您需要形如mystring[start:start+length]
的子字符串。
那么,start
和length
需要什么值?
start
必须...
- 包括第一个字符,以覆盖所有子字符串:
start in range(0, ...)
。
- 不映射到短的子字符串,因此可以在结尾前停止
min_length
个字符:start in range(..., len(mystring) - min_length + 1)
。
length
必须...
- 覆盖长度为4的最短子字符串:
length in range(min_length, ...)
。
- 不超过索引
i
之后的剩余字符串:length in range(..., len(mystring) - i + 1))
+1
的项来自将长度(≥1)转换为索引(≥0)。您可以将所有内容放入单个表达式中:
substrings = [
mystring[i:i+j]
for i in range(0, len(mystring) - min_length + 1)
for j in range(min_length, len(mystring) - i + 1)
]
2. 计算子字符串数量
显然,你想为每个子字符串保持一个计数。为每个特定对象保留 任何东西 都是 dict
设计的初衷。所以你应该在 dict
中使用子字符串作为键,计数作为值。本质上,这对应于以下内容:
counts = {}
for substring in substrings:
try: # increase count for existing keys, set for new keys
counts[substring] += 1
except KeyError:
counts[substring] = 1
您可以将您的子字符串
简单地输入到collections.Counter
中,它会生成类似于上面的内容。
>>> counts = collections.Counter(substrings)
>>> print(counts)
Counter({'abcd': 2, 'abcdt': 1, 'abcdth': 1, 'abcdthi': 1, 'abcdthis': 1, ...})
注意重复出现的'abcd'
如何映射到数量为2。
3. 过滤重复的子字符串
现在您有了每个子字符串及其计数。您需要删除非重复的子字符串-即其中计数为1的子字符串。
Python提供了几种构造用于过滤,具体取决于您想要的输出。如果counts
是一个常规的dict
,这些也可以工作:
>>> list(filter(lambda key: counts[key] > 1, counts))
['abcd', 'text', 'samp', 'sampl', 'sample', 'ampl', 'ample', 'mple']
>>> {key: value for key, value in counts.items() if value > 1}
{'abcd': 2, 'ampl': 2, 'ample': 2, 'mple': 2, 'samp': 2, 'sampl': 2, 'sample': 2, 'text': 2}
使用Python基本数据类型
Python提供了一些基本数据类型,让你能够更高效地完成这个任务。
使用生成器构建子字符串。生成器会即时生成其成员,所以你永远不需要将它们全部存储在内存中。在你的应用场景中,可以使用生成器表达式:
substrings = (
mystring[i:i+j]
for i in range(0, len(mystring) - min_length + 1)
for j in range(min_length, len(mystring) - i + 1)
)
使用现有的计数器实现。Python提供了一个类似于dict
的容器,用于计算其成员数量:collections.Counter
可以直接处理您的子字符串生成器。特别是在较新的版本中,这种方法更加高效。 counts = collections.Counter(substrings)
您可以利用 Python 的惰性过滤器,仅检查一个子字符串。内置的 filter 函数或其他生成器表达式可以一次生成一个结果,而无需在内存中存储它们所有的内容。
for substring in filter(lambda key: counts[key] > 1, counts):
print(substring, 'occurs', counts[substring], 'times')