Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Баавгай ба тэмдэгт мөр
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Баавгайд Англи жижиг үсэгнээс бүтсэн $s = s_{1}s_{2}... s_{|s|}$ ($|s|$ бол тэмдэгт мөрийн урт) тэмдэгт мөр байна. Баавгай $x(i, j) = s_{i}s_{i + 1}... s_{j}$ нь хамгийн багадаа нэг "$bear$" дэд тэмдэгт мөрийг агуулсан байх $i, j$ $(1 ≤ i ≤ j ≤ |s|)$ хосуудын тоог олохыг хүссэн.
Хэрвээ $(i ≤ k ≤ j - 3)$ ба $s_{k} = b$, $s_{k + 1} = e$, $s_{k + 2} = a$, $s_{k + 3} = r$ байх $k$ индекс байдаг бол $x(i, j)$ тэмдэгт мөр нь "$bear$" тэмдэгт мөрийг агуулна.
Байвгайд өгөгдсөн асуудлыг даван туулахад нь тусал.
Оролт
Эхний мөр нь хоосон биш $s$ $(1 ≤ |s| ≤ 5000)$ тэмдэгт мөрийг агуулна. Тэмдэгт мөр нь зөвхөн Англи жижиг үсэгнээс бүрдэнэ.
Гаралт
Асуултын хариулт болох нэг тоо хэвлэнэ.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
bearbtear
Гаралт
6
Оролт
bearaabearc
Гаралт
20
Тэмдэглэл
Эхний жишээнд, дараах $(i, j)$ хосууд тохирно: $(1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9)$.
Хоёр дахь жишээнд, дараах $(i, j)$ хосууд тохирно: $(1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 10), (2, 11), (3, 10), (3, 11), (4, 10), (4, 11), (5, 10), (5, 11), (6, 10), (6, 11), (7, 10), (7, 11)$.