1752 - nr aparitii rec

Cerința

Scrieţi în limbajul Python 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.

Date de intrare

Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

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

Exemplu

nr_aparitii("maimuta_samurai", "mu") = 2

Rezolvare

Pentru a implementa această funcție, putem folosi o metodă de căutare a șirului secventa în șirul sir, care presupune compararea caracter cu caracter a celor două șiruri și în cazul în care găsim o potrivire parțială, continuăm căutarea cu restul caracterelor până când găsim sau nu întregul șir secventa.

Pentru a implementa această metodă, putem folosi o funcție auxiliară cauta care primește ca parametrii începutul șirului sir și începutul șirului secventa, și returnează 1 dacă șirul secventa apare în șirul sir începând cu poziția dată, sau 0 în caz contrar. Apoi, putem defini funcția nr_aparitii care folosește această funcție pentru a căuta secvența în șir și, în cazul în care o găsește, mărește numărul de apariții și continuă căutarea începând cu poziția următoare din șirul sir.

În cele ce urmează, vom implementa această soluție și vom adăuga funcții de validare și main pentru a verifica și executa codul.

def validare_input(sir, secventa):
   if ' ' in sir or ' ' in secventa:
       return False
   if len(sir) > 1000 or len(secventa) > 1000:
       return False
   return True
def nr_aparitii(sir, secventa):
   if not validare_input(sir, secventa):
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   n = len(sir)
   m = len(secventa)
   if n < m:
       return 0
   if sir[:m] == secventa:
       return 1 + nr_aparitii(sir[m:], secventa)
   else:
       return nr_aparitii(sir[1:], secventa)
def main():
   sir = input("Introduceti sirul: ")
   secventa = input("Introduceti secventa: ")
   if validare_input(sir, secventa):
       print("Datele de intrare corespund restricțiilor impuse.")
       print("Numarul de aparitii ale secventei in sir este:", nr_aparitii(sir, secventa))
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")
if __name__ == '__main__':
   main()