E. Алдаа засах

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

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

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

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

Хүмүүс хайж буй зүйлээ шивэх үед гаргадаг алдаанд дүн шинжилгээ хийх нь тун сонирхолтой цогц ажил юм. Хэрэглэгчийн шивсэн хүсэлтээс яг юу хайхыг хүссэнийг тодорхой мэдэж чадахгүй тул олон төрлийн хьюристик шинжилгээ хэрэглэдэг.

Поликарпт хоёр үг өгөгдсөнөөр тодорхой шивэлтийн алдааны дагуу уг хоёр үг ижил үгнээс үүсч болох эсэхийг мэддэг програм бичих хэрэгтэй болжээ. Поликарпус хэлэхдээ "Хамгийн энгийн шивэлтийн алдаа бол үгийг шивэхдээ яг нэг үсэг орхигдуулах юм" гэжээ.

Ижилхэн $n$ урттай $S$ ба $T$ тэмдэгт мөрүүд өгөгдсөнөөр яг нэг үсэг арилган уг хоёр тэмдэгт мөрийн алийг нь ч гаргаж чаддаг $n + 1$ урттай хэдэн $W$ тэмдэгт мөр байж болохыг олдог програм зохио. $S$ ба $T$ нар нь Англи цагаан толгойн жижиг үсгүүдээс бүтнэ. $W$ мөн Англи цагаан толгойн жижиг үсгүүдээс бүтсэн байх ёстой.

Оролт

Эхний мөрөнд $S$ ба $T$ тэмдэгт мөрүүдийн уртыг илэрхийлэх $n$ ($1 ≤ n ≤ 100 000$) гэсэн бүхэл тоо байна.

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

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

$S$ ба $T$ нар нь Англи цагаан толгойн жижиг үсгүүдээс бүтнэ. Мөн хоорондоо ялгаатай байх болно.

Гаралт

Уг шивэлтийн алдаагаар $S$ болон $T$-г гаргаж болдог байх $W$ гэсэн тэмдэгт мөрүүдийн тоог хэвлэ.

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

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

Оролт
7
reading
trading
Гаралт
1
Оролт
5
sweet
sheep
Гаралт
0
Оролт
3
toy
try
Гаралт
2

Тэмдэглэл

Эхний жишээнд "treading" гэсэн үг л нөхцөл хангана (устгагдах үсгүүдийг тодоор тэмдэглэв).

Хоёр дахь жишээнд ямар ч тэмдэгт мөрөөс нэг үсэг хасах замаар уг хоёр тэмдэгт мөрийг гаргах боломж байхгүй.

Гурав дахь жишээнд "to*ry" ба "tr*oy" тэмдэгт мөрүүд нөхцөл хангана.

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