D. Угтварууд болон дагаврууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Таньд $s = s_{1}s_{2}...s_{|s|}$ тэмдэгт мөр байгаа ба $|s|$ нь $s$ тэмдэгт мөрийн урт, $s_{i}$ бол $i$-р тэмдэгт.

Хэд хэдэн тодорхойлолтыг танилцуулъя:

  • $s$ тэмдэгт мөрийн дэд тэмдэгт мөр $s[i..j]$ $(1 ≤ i ≤ j ≤ |s|)$ бол $s_{i}s_{i + 1}...s_{j}$.
  • $s$ тэмдэгт мөрийн $l$ $(1 ≤ l ≤ |s|)$ урттай угтвар бол $s[1..l]$ тэмдэгт мөр.
  • $s$ тэмдэгт мөрийн $l$ $(1 ≤ l ≤ |s|)$ урттай дагавар бол $s[|s| - l + 1..|s|]$ тэмдэгт мөр.

Таны даалгавар бол $s$ тэмдэгт мөрийн ямар нэг угтвартай тохирох $s$ тэмдэгт мөрийн дагаваруудыг олох ба энэ дэд тэмдэгт мөр нь $s$-д хэдэн удаа тохиолдсон тоог хэвлэнэ.

Оролт

Нэг мөрөнд $s$ тэмдэгт мөрийн тэмдэгтүүдийн дарааллыг $s_{1}s_{2}...s_{|s|}$ $(1 ≤ |s| ≤ 10^{5})$ оруулна. Тэмдэгт мөр нь зөвхөн Англи жижиг үсгүүдээс тогтоно.

Гаралт

Эхний мөрөнд $k$ $(0 ≤ k ≤ |s|)$ бүхэл тоог хэвлэнэ. Энэ нь $s$ тэмдэгт мөрийн дагаварт тохирох угтваруудын тоо. Дараа нь $k$ мөрүүд хэвлэх бөгөөд, мөр бүр нь $l_{i}$ $c_{i}$ хоёр бүхэл тоо хэвлэнэ. $l_{i}$ $c_{i}$ тоонууд нь $l_{i}$ урттай угтварт тохирох $l_{i}$ урттай дагавар бөгөөд дэд тэмдэгт мөр нь $s$-д $c_{i}$ удаа тохиолдоно гэсэн утгатай. $l_{i}$ $c_{i}$ хосуудыг $l_{i}$-н өсөх дарааллаар хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
ABACABA
Гаралт
3
1 4
3 2
7 1
Оролт
AAA
Гаралт
3
1 3
2 2
3 1
Сэтгэгдлүүдийг ачааллаж байна...