D. Мэссэнжэр

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

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

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

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

"Блэйк Технологи" компанийн ажилчид онцгой "Блэйк Мэссэнжэр" мэссэж бичих программыг ашигладаг. Бүх ажилчид энэ програмд дуртай ба тогтмол ашигладаг. Гэсэн хэдий ч зарим чухал давуу талууд дутагдаж байгаа. Жишээлбэл, олон хэрэглэгчид мэссэжийн түүхээсээ хайлт хийх боломжтой байхыг хүсдэг. Аль хэдийнээ энэ давуу талыг хамгийн ойрын шинэчлэлт дээрээ нэмнэ гээд зарлачихсан байхад хөгжүүлэгчид зарим асуудалтай тулгарсан ба эдгээрийг шийдвэрлэхэд зөвхөн та туслаж чадах байх.

Бүх мэссэжүүд Англи цагаан толгойн жижиг үсгүүдээс бүрдсэн тэмдэгт мөрүүдээр дүрслэгддэг. Сүлжээний ачааллыг багасгахын тулд тэмдэгт мөрүүдийг тусгай шахсан хэлбэрт оруулсан. Шахалтын алгоритм нь дараах байдлаар ажилладаг: тэмдэгт мөр нь $n$ блокын хэлхээ хэлбэрээр дүрслэгддэг, блок бүр тэнцүү тэмдэгт агуулна. Нэг блок $(l_{i}, c_{i})$ хослолоор тодорхойлогдож болох ба $l_{i}$ нь $i$-р блокын урт ба $c_{i}$ нь харгалзах үсэг. Тэмдэгт мөр $s$ нь хослолуудын дарааллаар бичигдэж болно .

Таны ажил бол шахагдсан хоёр тэмдэгт мөр $t$, $s$-н хувьд $t$ дотор хэдэн $s$ байж болохыг ол. Хөгжүүлэгчид хэдэн ч өөр тохиолдол байж болохыг мэдэх учраас нийт тоог нь олохыг хүсч байна. Хэрвээ $t_{i}$ нь $t$-ийн $i$-р тэмдэгт бол $t_{p}t_{p + 1}...t_{p + |s| - 1} = s$-н хувьд $p$ бол $s$-ийн $t$ дахь зарим тохиолдлуудын эхлэх цэг.

Тэмдэгт мөрийг шахсан хэлбэрт харуулах нь давтагдашгүй биш байж магадгүй. Жишээлбэл "$aaaa$" тэмдэгт мөрийн хувьд дараах хэлбэрүүдээр өгөгдөж магадгүй , , ...

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 200 000$) байх ба харгалзан $t$ болон $s$ тэмдэгт мөрүүдийн блокийн тоо.

Хоёр дахь мөрөнд $t$ тэмдэгт мөрийн $n$ ширхэг хэсгүүд "$l_{i}$-$c_{i}$" ($1 ≤ l_{i} ≤ 1 000 000$) хэлбэрээр илэрхийлэгдэх ба $i$-р хэсгийн урт ба харгалзах Англи цагаан толгойн жижиг үсэг.

Гурав дахь мөрөнд $s$ тэмдэгт мөрийн $m$ ширхэг хэсгүүд "$l_{i}$-$c_{i}$" ($1 ≤ l_{i} ≤ 1 000 000$) хэлбэрээр илэрхийлэгдэх ба $i$-р хэсгийн урт ба харгалзах Англи цагаан толгойн жижиг үсэг.

Гаралт

$s$-н $t$-д тохиолдох тохиолдлын тоо болох бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 3
3-a 2-b 4-c 3-a 2-c
2-a 2-b 1-c
Гаралт
1
Оролт
6 1
3-a 6-b 7-a 4-c 8-e 2-a
3-a
Гаралт
6
Оролт
5 5
1-h 1-e 1-l 1-l 1-o
1-w 1-o 1-r 1-l 1-d
Гаралт
0

Тэмдэглэл

Эхний жишээн дээр тэмдэгт мөр $t$ = "$aaabbccccaaacc$" ба $s$ = "$aabbc$". $s$-н $t$-д тохиолдох ганц тохиолдол нь эхлэлийн цэг $p = 2$ байх явдал юм.

Хоёр дахь жишээн дээр тэмдэгт мөр $t$ = "$aaabbbbbbaaaaaaacccceeeeeeeeaa$" ба $s$ = "$aaa$". $s$-н $t$-д тохиолдох тохиолдлууд нь $p = 1$, $p = 10$, $p = 11$, $p = 12$, $p = 13$ ба $p = 14$ юм.

Сэтгэгдлүүдийг ачааллаж байна...