D. Баримжаалсан хайлт

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

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

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

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

Леонид хүний генийн кодыг тайлж унших төсөл дээр ажиллаж байлаа. Тэр одоо "A", "T", "G", "C" үсэгнүүдээс бүрдсэн нэлээд урт тэмдэгт мөрөөс тодорхой бүтэцтэй дарааллыг олох төвөгтэй асуудлыг шийдвэрлэхээр ажиллаж байна.

Дараах тохиолдлыг авч үзье. $S$ тэмдэгт мөрөөр бичигдсэн хүний ДНХ-ийн гинжин хэлхээний хэсэг байна. Хэсэгт дүн шинжилгээ хийхийн тулд та $S$ тэмдэгт мөрд байгаа $T$ тэмдэгт мөр бүрийг олох хэрэгтэй. Гэхдээ анхны гинжин хэлхээний хэсэг бага зэргийн мутаци агуулж байж болох учраас энэ нь хэсгийг олох ажлыг хүндрэлтэй болгож байна. Леонид энэ асуудлыг шийдэхийн тулд дараах аргыг санал болгосон юм.

Алдааны хязгаар болох $k ≥ 0$ бүхэл тоог бичиж үзье. $S$ тэмдэгт мөрийн $i$-р байрлалд $T$ тэмдэгт мөрийг тавьсаны дараа $T$ тэмдэгт мөрийн тэмдэгт бүр нь хамгийн ихдээ $k$ зайд $S$ тэмдэгт мөрийн ижил утга бүхий ямар нэг тэмдэгттэй харгалздаг бол $S$ тэмдэгт мөрийн $i$ ($1 ≤ i ≤ |S| - |T| + 1$)-р байрлалд $T$ тэмдэгт мөр гарч ирж байна гэж хэлж болно. Томъёолбол аливаа $j$-н ($1 ≤ j ≤ |T|$) хувьд $|(i + j - 1) - p| ≤ k$ ба $S[p] = T[j]$ байх $p$ ($1 ≤ p ≤ |S|$) байна.

Жишээ нь, өгөгдсөн тодорхойлолтын дагуу "AGCAATTCAT" тэмдэгт мөрийн $2$, $3$, $6$-р байрлалуудад "ACAT" тэмдэгт мөр гарч ирж байна.

$k = 0$ үед тэмдэгт мөрд тэмдэгт мөр гарч ирэх өгөгдсөн тодорхойлолт энгийн тодорхойлолт болж хувирна гэдгийг санаарай.

Өгөгдсөн алдааны хязгаарлалтаар $S$ тэмдэгт мөрд $T$ тэмдэгт мөр гарч ирэх хэдэн байрлал байгааг тооцоолоход Леонидод туслаарай.

Оролт

Оролтын эхний мөрөнд $|S|, |T|, k$ ($1 ≤ |T| ≤ |S| ≤ 200 000$, $0 ≤ k ≤ 200 000$) гурван бүхэл тоо байна. Эдгээр нь $S$ тэмдэгт мөрийн урт, $T$ тэмдэгт мөрийн урт болон алдааны хязгаарын тоо юм.

Хоёр дахь мөрөнд $S$ тэмдэгт мөр байна.

Гурав дахь мөрөнд $T$ тэмдэгт мөр байна.

Хоёр тэмдэгт мөр "A", "T", "G", "C" том үсэгнүүдээс л бүрдэнэ.

Гаралт

Өгөгдсөн тодорхойлолтын дагуу $k$ алдааны хязгаарлалттайгаар $S$ тэмдэгт мөрд $T$ тэмдэгт мөр гарч ирэх боломжийн тоог хэвлэнэ үү.

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

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

Оролт
10 4 1
AGCAATTCAT
ACAT
Гаралт
3

Тэмдэглэл

Хэрвээ та хүний генийн бүтэцийн талаар бодлогын зохиогчоос илүү мэддэг, мөн Леонидын сэдсэн арга ач холбогдолгүй санагдаж байгаа бол дээр дурдсан бүх зүйлийг чухалчлан авч үзэхгүй байна уу.

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