C. Анаграм хайсан нь

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

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

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

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

$s$ тэмдэгт мөрийн тэмдэгтүүдийн байрыг солих замаар $t$ тэмдэгт мөрийг гаргаж ирж чаддаг бол $t$ тэмдэгт мөрийг $s$ тэмдэгт мөрийн анаграм гэнэ. Жишээ нь "aab" нь "aba"-н анаграм ба "aaa" нь биш юм.

Хэрэв $t$ тэмдэгт мөр $s$ тэмдэгт мөрийн аль нэг байрлалаас нь эхлэн тасралтгүй уншигдаж болж байвал $t$ тэмдэгт мөрийг $s$ тэмдэгт мөрийн дэд тэмдэгт мөр гэнэ. Жишээ нь "aba" тэмдэгт мөр зургаан дэд тэмдэгт мөртэй: "a", "b", "a", "ab", "ba", "aba".

Чамд Латин цагаан толгойн жижиг үсгүүд болон "?" тэмдэгтээс тогтох $s$ тэмдэгт мөр өгөгдөнө. Мөн чамд Латин цагаан толгойн жижиг үсгүүдээс тогтох $p$ тэмдэгт мөр өгөгдөнө. Тэмдэгт мөрийн "?" тэмдэгт бүрийг Латин цагаан толгойн жижиг үсгээр солих замаар $p$ тэмдэгт мөрийн аль нэг анаграмыг гаргаж чаддаг бол тэр тэмдэгт мөрийг сайн тэмдэгт мөр гэе. Жишээ нь $p$ = "aba" үед "a??" нь сайн ба "?bc" нь сайн биш юм.

Чиний даалгавар бол $s$-ийн дэд тэмдэгт мөрүүдийн хэд нь сайн тэмдэгт мөр болохыг олох юм. (Ижил төстэй дэд тэмдэгт мөрүүд олон удаа тоологдож болохыг анхаараарай).

Оролт

Эхний мөрөнд Латин цагаан толгойн жижиг үсгүүд болон "?" тэмдэгтээс тогтох $s$ гэсэн хоосон биш $10^{5}$-ээс хэтрэхгүй урттай тэмдэгт мөр өгөгдөнө. Хоёр дахь мөрөнд Латин цагаан толгойн жижиг үсгүүдээс тогтох $10^{5}$-аас хэтрэхгүй урттай $p$ тэмдэгт мөр байна. $p$-ийн урт $s$-ийн уртаас их байж болохыг анхаарна уу.

Гаралт

$s$ тэмдэгт мөрийн сайн дэд тэмдэгт мөрийн тоог хэвлэ.

Дэд тэмдэгт мөрүүдийн байрлал өөр бол ялгаатайд тооцогдоно. Тиймээс хэрэв ямар нэгэн тэмдэгт мөр олон удаа тааралдвал тэр бүртээ дэд тэмдэгт мөр гэж тоологдоно.

Орчуулсан: Бат-Од

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

Оролт
bb??x???
aab
Гаралт
2
Оролт
ab?c
acb
Гаралт
2

Тэмдэглэл

Эхний жишээг авч үзье. Энд $s$ тэмдэгт мөр хоёр сайн дэд тэмдэгт мөртэй:

  • "b??" - асуултын тэмдгийг сольсны дараа "baa" гэсэн сайн тэмдэгт мөр гаргаж чадна.
  • "???" - асуултын тэмдгийг сольсны дараа "baa" гэсэн сайн тэмдэгт мөр гаргаж чадна.

Хоёр дахь жишээг авч үзье. Энд $s$ тэмдэгт мөр хоёр сайн тэмдэгт мөртэй:

  • "ab?" - "?" тэмдэгтийг "c" тэмдэгтээр солино.
  • "b?c" - "?" тэмдэгтийг "a" тэмдэгтээр солино.
Сэтгэгдлүүдийг ачааллаж байна...