本文共 1003 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到由小写英文字母组成的字符串中包含子串“bear”的所有可能的子串对数。具体来说，我们需要计算满足条件的(i, j)对数，其中子串s[i...j]包含至少一个“bear”。

方法思路

解决代码

import bisect
s = input().strip()
bear_positions = []
n = len(s)
for k in range(n - 3):
    if s[k] == 'b' and s[k+1] == 'e' and s[k+2] == 'a' and s[k+3] == 'r':
        bear_positions.append(k + 1)  # 转换为1-based索引
count = 0
for i in range(1, n + 1):
    for j in range(i + 3, n + 1):
        low = i
        high = j - 3
        left = bisect.bisect_left(bear_positions, low)
        right = bisect.bisect_right(bear_positions, high)
        if right > left:
            count += 1
print(count)

代码解释

这种方法通过预处理和二分查找，有效地减少了重复检查，提高了效率，使得在合理的时间内解决问题。