subbit

Subsir Binar

== include(page="template/taskheader" task_id="subbit") ==

Poveste şi cerinţă...

Se considera sirul binar $A = "011011100..."$, format prin concatenarea reprezentarilor binare a numerelor naturale de la $0$ la infinit. Pozitia de inceput se numeroteaza cu $1$. Se da un sir binar $B$ de lungime $N$. Sa se afiseze cea mai mica pozitie $p$ astfel incat sirul $B$ se gaseste ca subsir in sirul $A[1..p]$.
Spunem ca sirul $T$ de lungime $K$ este un subsir al lui $S$ daca toate caraterele din sirul $T$ apar in aceeasi ordine in sirul $S$ pe pozitii nu neaparat consecutive. Mai exact, $T$ este un subsir al lui $S$ daca exista indicii
$1 &le; i{~1~} < i{~2~} < ... < i{~K~} &le; |S|$ astfel incat $T{~1~} = S{~i{~1~}~}, T{~2~} = S{~i{~2~}~}, ..., T{~K~} = S{~i{~K~}~}$

h2. Date de intrare

Fişierul de intrare $subbit.in$ ...

Fişierul de intrare $subbit.in$ contine pe prima linie sirul binar $B$.

h2. Date de ieşire

În fişierul de ieşire $subbit.out$ ...

Fişierul de ieşire $subbit.out$ trebuie sa contina pe prima linie numarul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ |B| ≤ 5.000.000$

h2. Exemplu
table(example). |_. subbit.in |_. subbit.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 00100101
| 12

|
h3. Explicaţie

...

Primele $22$ caractere din sirul $A$ sunt "{*0*}11{*0*}1{*1*}1{*00101*}1101111000".

== include(page="template/taskfooter" task_id="subbit") ==