这是一个相对优化的朴素算法。首先，将每个序列转换为所有ngram的集合。然后，将所有集合相交，并在相交中找到最长的ngram。
from functools import partial, reducefrom itertools import chainfrom typing import Iteratordef ngram(seq: str, n: int) -> Iterator[str]: return (seq[i: i+n] for i in range(0, len(seq)-n+1))def allngram(seq: str) -> set: lengths = range(len(seq)) ngrams = map(partial(ngram, seq), lengths) return set(chain.from_iterable(ngrams))sequences = ["brownasdfoersjumps", "foxsxzxasis12sa[[#brown", "thissasbrownxc-34a@s;"]seqs_ngrams = map(allngram, sequences)intersection = reduce(set.intersection, seqs_ngrams)longest = max(intersection, key=len) # -> brown
虽然这可能使您了解短序列，但此算法在长序列上效率极低。如果序列很长，则可以添加启发式方法以限制最大可能的ngram长度（即，可能的最长公共子串）。这种启发式方法的一个显而易见的价值可能是最短序列的长度。
def allngram(seq: str, minn=1, maxn=None) -> Iterator[str]: lengths = range(minn, maxn) if maxn else range(minn, len(seq)) ngrams = map(partial(ngram, seq), lengths) return set(chain.from_iterable(ngrams))sequences = ["brownasdfoersjumps", "foxsxzxasis12sa[[#brown", "thissasbrownxc-34a@s;"]maxn = min(map(len, sequences))seqs_ngrams = map(partial(allngram, maxn=maxn), sequences)intersection = reduce(set.intersection, seqs_ngrams)longest = max(intersection, key=len) # -> brown
这可能仍会花费太长时间（或使您的计算机用完RAM），因此您可能需要阅读一些最佳算法（请参阅我在评论中留给您的问题的链接）。
更新资料
计算每个ngram出现的字符串数
from collections import Countersequences = ["brownasdfoersjumps", "foxsxzxasis12sa[[#brown", "thissasbrownxc-34a@s;"]seqs_ngrams = map(allngram, sequences)counts = Counter(chain.from_iterable(seqs_ngrams))
Counter是的子类
dict，因此其实例具有相似的接口：
print(counts)Counter({'#': 1, '#b': 1, '#br': 1, '#bro': 1, '#brow': 1, '#brown': 1, '-': 1, '-3': 1, '-34': 1, '-34a': 1, '-34a@': 1, '-34a@s': 1, '-34a@s;': 1, ...您可以过滤计数以使子字符串至少出现在
n字符串中：
{string: count for string, count in counts.items()if count >= n}
