B. Тиндекс.Бром

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

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

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

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

Тиндекс ахиад л хүчтэй өрсөлдөөнийг үзүүлж байв. Зүүзл Хром-ыг гарах үед хүмүүс хүлээн авч байсантай ижлээр шинэ броузэр Тиндекс.Бром-ыг хүлээн авав!

Уг шинэ броузэр-ийн алдар нэр нь өдрөөс өдөрт өсөж байлаа. Гэхдээ үүний нууц нь зөвхөн Тиндекс.Бар-ыг (Тиндекс.Боттл-ыг худалдан авсны дараа Тиндекс.Бар нь автоматаар танд 1664 оны хамгийн сайн конъяк-ыг аягалж өгөх бөгөөд та үүнийг USB оролтын хэсгээс авч уух боломжтой юм) суулгасанд биш байлаа. Үүний учир нь энэ броузер хүмүүсийн сэтгэлд ихэд хүрсэнтэй холбоотой байсан юм.

Жишээлбэл уг броузер нь автомат хаяг засах системтэй байв. Та codeforces гэж бичихийн оронд codehorses гэж бичиж байсан уу? Зүүзл Хром харамсалтай нь уг вэб хаяг оршин байхгүй байна гэж үзүүлэх юм. Харин Тиндекс.Бром нь автоматаар хамгийн ойролцоо вэб хаягийг хайж олон танийг уг хаяг уруу нэвтрүүлнэ. Үнэхээр гайхалтай!

Уг гайхалтай функц нь хэрхэн ажилладаг бол? Үнэхээр энгийн! Боломжит хаяг бүрийн хувьд алдааны $F$ функц нь дараах дүрмийн дагуу ажиллах юм:

  • $c$ гэсэн боломжит хаягийн $c_{i}$ үсэг бүрийн хувьд хэрэглэгчийн оруулсан хаяг ($s$) доторх $c_{i}$ үсэгтэй хамгийн ойрхон байх $j$ байрлалыг хайж олно. Эдгээрийн байрлалуудын абсолют зөрүү болох $|i - j|$-ыг $F$ дээр нэмэх юм. Түүнчлэн $i$ ($1 ≤ i ≤ |c|$) бүрийн хувьд $c_{i} = s_{j}$ байх $j$ гэсэн байрлал нь сонгогдсон байх бөгөөд $|i - j|$ нь боломжит хамгийн бага байх ёстой ажээ.
  • Хэрэв хэрэглэгчийн оруулсан хаяг дотор $c_{i}$ гэсэн үсэг байхгүй байвал боломжит хаягийн урт $|c|$-г $F$ дээр нэмнэ.

Бүх боломжит хаягуудын хувьд алдааны функцийн утгуудыг тооцоолсны дараа хамгийн тохиромжтой нэгийг нь хайж олох юм.

Дээр дүрсэлсэн аргын тусгай шинж чанарыг сайтар ойлгохын тулд та хэрэглэгчийн оруулсан хаяг болон боломжит хаягуудын ямар нэгэн олонлогийн хувьд $F$ функцийг тооцоолох алгоритмыг ойлгох хэрэгтэй юм. Танд амжилт хүсье!

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 10^{5}$) өгөгдөнө. Эдгээр нь боломжит хаягуудын тоо болон хэрэглэгчийн оруулсан хаягийн уртыг тус тус илэрхийлнэ. Дараагийн мөрөнд $k$ ширхэг Латин жижиг үсгүүд өгөгдөнө. Эдгээр нь хэрэглэгчийн оруулсан хаяг буюу $s$-г илэрхийлнэ. Дараа нь өгөгдөх мөрүүдийн $i$-р ($1 ≤ i ≤ n$) мөр болгонд Латин жижиг үсгүүдийн хоосон биш дараалал өгөгдөх юм. Эдгээр нь боломжит хаягуудыг илэрхийлнэ. Мөн эдгээр бүх мөрүүдийн нийт урт нь $2*10^{5}$-аас хэтрэхгүй байна.

Гаралт

Гаралтын $n$ ширхэг мөрийн мөр болгонд ганц тоо хэвлэх бөгөөд уг тоо нь тухайн боломжит хаяг сонгогдсон байх үеийн алдааны функцийн утгыг илэрхийлнэ.

C++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld гэсэн тодорхойлогчийг бүү хэрэглэнэ үү. Харин use cout эсвэл %I64d гэсэн тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

Орчуулсан: Баатархүү

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

Оролт
2 10
codeforces
codeforces
codehorses
Гаралт
0
12
Оролт
9 9
vkontakte
vcontacte
vkontrakte
vkollapse
vkrokodile
vtopke
vkapuste
vpechke
vk
vcodeforcese
Гаралт
18
14
36
47
14
29
30
0
84
Сэтгэгдлүүдийг ачааллаж байна...