Dinti

Fie inv(s) inversul sirului s (spre exemplu: inv(100) = 011). Fie S un sir determinat de L caractere consecutive din sirul A. Putem observa ca inv(S) si orice alt sir obtinut din inv(S) prin modificarea oricator valori 1 din inv(S) in 0 se potriveste peste S (exemplu: peste S = 100 se potrivesc 011, 001, 010, si 000).

Numarul total de siruri ce se pot potrivi peste A nu depaseste 2^L asa ca putem tine un vector V, de valori adevarat/fals de marime 2^L,
astfel incat V[cod(s)] = 1/0 daca sirul s se poate suprapune peste sirul A ( cod(s) reprezinta codificarea sirului s intr-un numar in baza 10 a carei reprezentare binara este egala cu sirul s). Ca sa obtinem acest vector putem lua pe rand toate sirurile S, parcurgand sirul A si tinand ultimele L caractere, si printr-un backtracking sa obtinem toate valorile ce se pot potrivi peste S (calculam inv(S) si apoi schimbam prin backtracking 1-urile in 0-uri in toate modurile posibile). Aceste siruri "bune" le putem stoca in sirul V si apoi putem raspunde la oricare intrebare in O(1). Singura problema este ca aceasta solutie are o complexitate prea mare (cam 3^L) si iese din timp. Pentru a nu folosi backtracking in generarea sirurilor bune vom face urmatorul lucru. Pentru toate sirurile S vom tine ca sir bun in V doar inv(S), iar dupa aceea vom folosi o dinamica pentru a afla toate sirurile bune. Pentru toate starile st, de la 2^L-1 la 0 (de la 11..1 la 00..0) putem zice ca daca V[st] = 1 atunci si V[st ^ (1 << k)] = 1, pentru toate k-urile pentru care st & (1 << k) != 0 (adica pentru toti bitii de 1 din st). Aceasta dinamica este echivalentul backtracking-ului pentru toate starile S.

Dupa ce obtinem sirul V putem raspunde la orice intrebare in O(1). Complexitatea totala a solutie este O( N + M + 2^L * L ).