Match


Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

Victor a scris intr-un caiet un sir de tip S de lungime L si N siruri de tip s de lungime M. El s-a gandit la un joc:

  • El poate lua un sir s si sa-l lipeasca peste sirul S.
  • El poate lipi sirul s peste sirul S doar daca sirul s si secventa peste care este lipit sunt echivalente.
  • Doua siruri lipite NU au voie sa se suprapuna.

Victor se intreaba: care este numarul maxim de siruri pe care le poate lipi?

Date de intrare

  • Pe prima linie se vor afla in ordine, L, N, si M.
  • Pe a doua linie se va afla sirul S.
  • Pe urmatoarele N linii se vor afla sirurile s.

Date de iesire

  • Pe prima linie se va afisa rezultatul cerut.

Restrictii si precizari

  • 1 <= N <= 10000.
  • 1 <= M <= 100.
  • 1 <= L <= 100000.
  • Un sir s poate fi lipit de mai multe ori.
  • Un sir s poate aparea de mai multe ori in lista de N siruri.
  • Toate sirurile contin doar litere mici ale alfabetului englez.

Exemple

Date de intrare
10 6 2
aabbccddee
aa
ab
bb
cd
ee
ee
Date de iesire
4
Precizari
  • Se pot lipi sirurile aa, bb, cd si ee respectand regulile jocului.
  • Se observa ca sirul ab nu poate fi lipit in acest caz deoarece s-ar suprapune cu celelalte siruri lipite.

Comments

There are no comments at the moment.