1752 - Nr aparitii recursive

Cerința

Scrieţi în limbajul c++ definiţia completă a funcţiei recursive nr_aparitii cu următorul antet:

unsigned nr_aparitii(char *sir, char *secventa)

ce returnează numărul de apariţii ale şirului de caractere secventa în şirul sir.

Restricții și precizări

• cele două şiruri nu conţin spaţii şi au cel mult 1000 de caractere
• biblioteca cstring (string.h) este deja inclusă la verificare

La rezolvarea acestei probleme am folosit limbajul python.

Exemplu 1

Introduceti sirul principal: maimuta_samurai

Introduceti secventa cautata: mu

Numarul de aparitii: 2

Exemplu 2

Introduceti sirul principal: boboci_bocanc

Introduceti secventa cautata: bo

Numarul de aparitii: 3

Exemplu 3

Introduceti sirul principal: mu

Introduceti secventa cautata: maimuta

Date de intrare invalide: Secventa cautata nu poate fi mai lunga decat sirul principal.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1752 nr_aparitii_rec

def nr_aparitii(sir, secventa):

   # Initializam numarul de aparitii
   aparitii = 0
   
   # Lungimile sirurilor
   lungime_sir = len(sir)
   lungime_secventa = len(secventa)

   # Parcurgem sirul
   for i in range(lungime_sir - lungime_secventa + 1):
       # Verificam daca secventa se potriveste incepând de la pozitia i
       if sir[i:i+lungime_secventa] == secventa:
           aparitii += 1

   return aparitii

def validate_input(sir, secventa):

   if not sir or not secventa:
       return False, "Sirul principal si secventa cautata nu pot fi goale."

   if len(secventa) > len(sir):
       return False, "Secventa cautata nu poate fi mai lunga decat sirul principal."

   return True, None

def main():

   sir_principal = input("Introduceti sirul principal: ")
   secventa_cautata = input("Introduceti secventa cautata: ")

   is_valid, error_message = validate_input(sir_principal, secventa_cautata)

   if not is_valid:
       print("Date de intrare invalide:", error_message)
       return

   rezultat = nr_aparitii(sir_principal, secventa_cautata)

   print("Numarul de aparitii:", rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>