Kezdőlap


Feladat:	S.145	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2020/szeptember, 360. oldal		PDF \| MathML
Témakör(ök):	Számítástechnika, informatika, Nehezebb feladat, Számítástudomány

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Van egy szótárunk $N$ db szóval. Azt szeretnénk tudni, hányféleképpen tudjuk a szótárból választott szavakat a dominóhoz hasonlóan összeilleszteni úgy, hogy azok $K$ betű hosszan átfedjék egymást. Tehát a kérdés: hány olyan $(i, j)$ rendezett számpár ( $1 \leq i, j \leq N$ ) van, melyre az $i$ -edik szó utolsó $K$ betűjéből alkotott sorozat megegyezik a $j$ -edik szó első $K$ betűjéből alkotott sorozattal.
Bemenet: az első sor tartalmazza az $N$ és $K$ számokat. A következő $N$ sor mindegyike egy, az angol ABC kisbetűiből álló (nem feltétlenül értelmes) szót tartalmaz.
Kimenet: a megfelelő összeillesztések, vagyis számpárok száma.
Példa:

\begin{matrix} Bemenet(a/jel sortörést helyettesít) & Kimenet \\ 4 2 / sapka / kalap / baba / bamba & 3 \end{matrix}

Korlátok:

2 \leq N \leq 10^{5}

1 \leq K \leq 100

, minden szó legalább

K

és legfeljebb 100 betű hosszú. Időkorlát: 1 mp.
Értékelés: a pontok 30%-a kapható

K = 1

esetén. A pontok további 30%-a kapható, ha

N \leq 100

.
Beküldendő egy s145.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.