Informatică, întrebare adresată de stephanieec, 9 ani în urmă

poate cineva sa puna algoritmul pentru verificarea unui sir ca este secventa, respectiv subsir?


stephanieec: de ex crescator

Răspunsuri la întrebare

Răspuns de headache
1
deci avem sirurile s1 si s2 , unde trebuie sa aflam daca s2 se gaseste in s1, cunoastem n lungimea lui s1 si m lungimea lui s2
k=0;
for(i=1,i<=n-m+1,i++)
{if(k!=0)
i=n-m+1;
if(s1[i]==s2[1])
for (j=2,j<=m,j++)
if(s2[j]!=s1[i+j-1])
j=m;
else 
if(j==m)
k=1;}
daca dupa rularea secventei acesteia k este 1 inseamna ca s2 este un subsir la lui s2 in caz contrar nu este, in primul for am pus conditia ca i sa mearga pana la n-m+1, deoerece nu are rost sa cauti un sir intr-un spatiu mai mic decat dimensiunile lui , astfel for-ul merge pana la ultima pozitie unde s-ar putea gasi capatul sirului s2, am pus acea conditie de terminare a primului for (if(k!=0)    i=n-m+1;) in caz ca s-a gasit s2 in s1, si inca o conditie de terminare in  al doilea for(if(s2[j]!=s1[i+j-1])  j=m;) in caz ca s-a gasit o parte din sir si apare o valoare care nu respecta regula, am pus acele 2 conditi pentru optimizarea timpului de rulaj 
Sper ca iti este de ajutor :))
Alte întrebări interesante