Codeforces: Good Bye 2013 - Problem D

[•manutruta]

Salut !

Imi spuneti va rog cum se face problema aceasta: http://codeforces.com/contest/379/problem/D ?
Tutorialul la runda respectiva e foarte vag si nu am reusit sa inteleg nimic din el, iar in comentrui e explicat ceva acolo, dar iar nu am reusit sa inteleg.

Help is very much appreciated !
Multumesc anticipat.
Manu

[•klamathix]

Din recurența pentru string poți găsi o recurență pentru numărul de apariții ale șirului AC in șirul final: nr[j] = nr[j - 1] + nr[j - 2] + overlap, unde overlap e 0 sau 1. Chestia e că dacă ai două stringuri X și Y, numărul de apariții "AC" în X + Y e suma aparițiilor din X și din Y + eventual încă o apariție pe mijloc, la concatenare, dacă X se termină în A și Y începe cu C.

Deci în primul rând ar trebui să-ți fixezi de câte ori apare AC în primele două șiruri. Apoi trebuie să te hotărăști dacă vrei să apară AC-uri noi pe mijloc. Dacă examinezi puțin cum se formează șirurile ai să vezi că chestia asta depinde exclusiv de primele și ultimele litere ale celor două șiruri inițiale.