CSES - Datatähti 2019 alku - Leimasin
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Haluat muodostaa merkkijonon, jonka pituus on nn merkkiä. Merkkijonon merkit on numeroitu 1,2,,n1,2,\dots,n, ja aluksi jokainen merkki on ?.

Käytössäsi on leimasin, jonka pituus on mm merkkiä. Voit joka siirrolla asettaa leimasimen johonkin merkkijonon kohtaan ja korvata merkkijonon merkit tällä alueella vastaavissa kohdissa olevilla leimasimen merkeillä. Leimasimen täytyy olla kokonaan merkkijonon sisällä joka siirrolla, eikä sen asentoa voi muuttaa.

Tehtäväsi on etsiä siirtosarja, jolla voit tuottaa halutun merkkijonon leimasimen avulla, tai todeta, että tämä ei ole mahdollista.

Syöte

Ensimmäisellä rivillä on merkkijono, jossa on nn merkkiä: tavoitteena oleva merkkijono.

Toisella rivillä on merkkijono, jossa on mm merkkiä: leimasin.

Molemmat merkkijonot muodostuvat merkeistä A–Z.

Tuloste

Tulosta ensin kokonaisluku kk: siirtojen määrä.

Tulosta sitten kk kokonaislukua, jotka kuvaavat siirrot järjestyksessä. Jokainen luku on välillä 1nm+11 \dots n-m+1 ja ilmaisee leimasimen vasemman kohdan.

Voit tulostaa minkä tahansa ratkaisun, jossa kk on enintään 10n10n. Jos mitään ratkaisua ei ole olemassa, tulosta vain luku 1-1.

Esimerkki 1

Syöte:

AABCACA
ABCA

Tuloste:

3
1 4 2

Selitys: Käytät leimasinta näin: ???????ABCA???ABCABCAAABCACA.

Esimerkki 2

Syöte:

AYBABTU
AB

Tuloste:

-1

Osatehtävä 1 (29 pistettä)

  • 1mn101 \le m \le n \le 10

Osatehtävä 2 (31 pistettä)

  • 1mn1001 \le m \le n \le 100

Osatehtävä 3 (40 pistettä)

  • 1mn10001 \le m \le n \le 1000