主页 / 问题 / 1543168
Accepted
Глеб
Asked:2023-09-29 18:35:59 +0000 UTC2023-09-29 18:35:59 +0000 UTC

查找重叠出现：计数函数崩溃

  • 772

任务是返回一个字符串在另一个字符串中出现的次数。问题很简单，我打算用函数来解决count()。一切似乎都很顺利：

>>> 'abcdefabc'.count('abc')
2
>>> 'aaa'.count('a')
3
>>> 'abca'.count('a')
2

然后突然：

>>> 'catcatcat'.count('catcat')
1

理论上，count()它应该返回字符串中子字符串出现的次数。事实证明，它返回不相交出现的次数。

问题：如果您需要返回出现的总数以及交集，该怎么办？也就是说，最后一个例子返回2?

python

3 个回答

  1. Best Answer

    正则表达式：

    len(re.findall('(?=catcat)', 'catcatcat'))

    答案取自英语 SO: String count with Overlapencions。

    那里还提出了其他几种解决方案。

    • 7

  2. 来自Python文档str.count：

    返回子字符串 sub 在范围 [ start , end ]中非重叠出现的次数。可选参数 start 和 end 被解释为切片表示法。

    如果 sub 为空，则返回字符之间的空行数，等于行长度加一。

    因此

    >>> 'catcatcat'.count('catcat')
1

    要使检查考虑交叉点，您可以实现以下方法：

    def count_overlapping_substrings(main_string, substring):
    count = 0
    start = 0
    while True:
        start = main_string.find(substring, start)  # Ищем следующее вхождение подстроки
        if start == -1:
            break
        count += 1
        start += 1  # Перемещаемся вправо, чтобы избежать бесконечного цикла при пересечениях
    return count

# Примеры использования:
print(count_overlapping_substrings('abcdefabc', 'abc'))  # Вывод: 2
print(count_overlapping_substrings('aaa', 'a'))  # Вывод: 3
print(count_overlapping_substrings('abca', 'a'))  # Вывод: 2
print(count_overlapping_substrings('catcatcat', 'catcat'))  # Вывод: 2

    还有这个单线

    import re
count = re.subn('(?=catcat)', '', 'catcatcat')[1]
print(count)
    • 3

  3. N+M对于使用 z 函数的时间。当处理大字符串时，线性时间非常有用。要在 200000 中搜索长度为 20000 的模式，时间为 0.36 秒，而常规模式为 31 秒。

    该模式被分配了一个在两行和正在执行搜索的pattern行中都缺失的字符。s如果某个地方的z函数的值与模式的长度一致lp，则找到一个出现（从位置开始的后缀i与前缀长度一致lp- 并且这个前缀就是模式）

    def cntoverlapped(s, pat):
    cnt = 0
    ps = pat + '$' + s
    lp = len(pat)
    n = len(ps)
    z = [0]*n
    l = 0
    r = 0
    for i in range(1, n):
        if (i <= r):
            z[i] = min (r-i+1, z[i-l])
        while (i+z[i] < n) and (ps[z[i]] == ps[i+z[i]]):
            z[i] += 1
        if (i+z[i]-1 > r):
            l = i
            r = i+z[i]-1
        if z[i]==lp:
            cnt += 1
    return cnt

print(cntoverlapped('ababababa', 'aba'))

>> 4
    • 3

相关问题