488 Strigat

[•DITzoneC]

Aici puteţi discuta despre problema Strigat.

[•pauldb]

Imi puteti spune ce are mai special ultimul test? Am vazut ca sunt si altii care se chinuie la el.

Later edit:
Mi-am gasit singur un test care-mi pica. Poate mai ajuta pe cineva:

Cod:

8 3
oooooo
1
oo
2
o
1

[•devilkind]

pai cuvantul e "oooooooo" si contine de 8 ori cuvantul "o" de 4 ori cuvantul "oo" si 1 singura data cuvnatul "oooooo". Deci gradul de spaima e 8*1+4*2+1=17.

[•bogdan2412]

contine de 8 ori "o", de 7 ori "oo" si de 3 ori "oooooo" de fapt. -> 25

[•devilkind]

da scuze am uitat de suprapunere

[•vanila_CPP]

kmp iese din timp 

[•wefgef]

Trebuie un automat finit .

[•amadaeus]

Cum se poate construi un automat finit determinist care accepta mai multe (N) cuvinte?
Adica... nu imi dau seama care sunt starile lui 

[•fireatmyself]

gasesti aici mai multe informatii.

[•amadaeus]

Citisem solutia oficiala si articolul despre automate finite. Am inteles cum se poate construi un automat finit care accepta un cuvant, dar, din cate inteleg din solutie, trebuie construit un automat care accepta mai multe cuvinte, iar starilor de acceptare le voi asocia apoi valorile "strigatului" (nu pot construi un automat avand ca stari cele 100 * 1000 valori posibile pentru strigat...). Dupa asta, dinamica e evidenta.
Insa, asa cum am spus, ramane de construit automatul pentru cele M cuvinte. 

LE: Cred ca m-am prins cum se face: pot lua ca stari toate prefixele cuvintelor, prefixele comune aparand o singura data. Astfel am maxim LTot stari, unde LTot este lungimea totala a cuvintelor. Constructia automatului se poate face astfel in O( LTot*|sigma| )

LE2: ...sau nu