Codeforces Round #804 (Div. 2)
3 өдрийн дараа |
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$ байна.