D. Дахиад ХУНД

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

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

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

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

Танд $n$ урттай $S$ тэмдэгт мөр өгөгдөнө. Тэмдэгт тус бүр нь Англи хэлний эхний $m$ жижиг үсгүүдийн аль нэг нь байна.

$S$ ба $T$ тэмдэгт мөрүүдийн Хамгийн урт нийтлэг дараалал (ХУНД) нь $n-1$ байх Англи хэлний эхний $m$ жижиг үсгүүдээс $n$ урттай, ялгаатай $T$ тэмдэгт мөр хэд үүсэхийг тооцоолоорой.

$S$ ба $T$-д аль алинд нь $C$ байх $S$ ба $T$ 2 тэмдэгт мөрийн ХУНД нь хамгийн урт $C$ тэмдэгт мөр байдгийг санаарай.

Оролт

Эхний мөр нь $S$ тэмдэгт мөрийн урт болон тэмдэгт мөр үүсгэх Англи хэлний эхний хэдэн тэмдэгт ашиглахыг харуулах $n$ ба $m$ 2 тоог агуулна.($1≤n≤100 000$, $2≤m≤26$).

2 дахь мөр нь $S$ тэмдэгт мөрийг агуулна.

Гаралт

Хариуг агуулах ганц мөрийг хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
3 3
aaa
Гаралт
6
Оролт
3 3
aab
Гаралт
11
Оролт
1 2
a
Гаралт
1
Оролт
10 9
abacadefgh
Гаралт
789

Тэмдэглэл

Эхний жишээнд, $6$ боломжит $T$ тэмдэгт мөр байна: $aab$, $aac$, $aba$, $aca$, $baa$, $caa$.

2 дахь жишээнд, $11$ боломжит $T$ тэмдэгт мөр байна: $aaa$, $aac$, $aba$, $abb$, $abc$, $aca$, $acb$, $baa$, $bab$, $caa$, $cab$.

3 дахь жишээнд, ганцхан боломжит $T$ тэмдэгт байх ба тэр нь $b$ байна.

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