h1(#potrivire). 'Potrivire':problema/potrivire

Solutie O(31*(N+M))

Solutie $O(31*(N+M))$

Fiecare subsecventa a sirului B, aflata intre 2 stelute o consideram un sir pentru care, folosind algoritmul KMP vom determina toate potrivirile acesteia in sirul A. Apoi, pe baza acestor rezultate se va construi solutia problemei, in asa fel incat pentru fiecare subsecventa a sirului B, aflata intre 2 stelute vom cauta cea mai din stanga potrivire in sirul A, dar in asa fel incat sa nu se suprapuna cu subsecventa anterioara.

Fiecare subsecventa a sirului $B$, aflata intre $2$ stelute o consideram un sir pentru care, folosind algoritmul KMP vom determina toate potrivirile acesteia in sirul $A$. Apoi, pe baza acestor rezultate se va construi solutia problemei, in asa fel incat pentru fiecare subsecventa a sirului $B$, aflata intre $2$ stelute vom cauta cea mai din stanga potrivire in sirul $A$, dar in asa fel incat sa nu se suprapuna cu subsecventa anterioara.