E. Сайн уриа

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

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

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

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

Бомбослав компаны шинэ лого болон сурталчилгааны уриа зохиодог ажил хийдэг. Компаны уриа нь нэрнийхээ дэд тэмдэгт мөр байх ёстой (дэд тэмдэгт мөр нь хоосон байж болохгүй). Жишээ нь: хэрвээ компаний нэр нь "$hornsandhoofs$" бол үүний уриа нь "$sand$" ба "$hor$" гэсэн дэд тэмдэгт мөрүүд байж болно. Харин "$e$" ба "$hornss$" тэмдэгт мөрүүд нь уриа болж болохгүй.

Зарим тохиолдолд компани өөрийн уриагаа сайжруулдаг. Хэрвээ уриа $B$ нь уриа $A$-ын дотор дор хаяж 2 удаа дэд тэмдэгт мөр хэлбэрээр орсон байх юм бол (эдгээр нь давхцаж болно) уриа $A$-г уриа $B$-ээсээ илүү сайн уриа гэж үзнэ. Жишээ нь: уриа $A$ = $abacaba$ нь уриа $B$ = "$ba$"-ээсээ илүү сайн, уриа $A$ =  "$abcbcbe$" нь уриа $B$ =  "$bcb$"-ээсээ илүү сайн, харин уриа $A$ = "$aaaaaa$" нь уриа $B$ =  "$aba$"-ээс илүү сайн байж чадахгүй.

Танд компаны нэр $w$ өгөгдөх бөгөөд таны даалгавар бол хамгийн олон уриануудыг $s_{1}, s_{2}, ..., s_{k}$ олж Бомбославт туслах юм. Нэг нөхцөл нь аль ч уриа нь өмнөх урианаасаа сайн байх ёстой (эхний уриаг тооцохгүй).

Оролт

Эхний мөрөнд компаний нэрний хэмжээ болох $n$ ($1 ≤ n ≤ 200 000$) нэг бүхэл тоо өгөгдөнө.

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

Гаралт

$w$ нэртэй компанид аль ч уриа нь өмнөх урианаасаа илүү сайн байх хамгийн ихдээ хэдэн уриа байх вэ? (эхний уриаг тооцохгүй) гэдэг асуултанд хариулах нэг бүхэл тоог хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
3
abc
Гаралт
1
Оролт
5
ddddd
Гаралт
5
Оролт
11
abracadabra
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...