Sujet 1 (A)

Étant donné deux chaînes de caractères C1 et C2 sur l'alphabet {A,B,C,D}, trouver le maximum de fois que l'on peut faire apparaître C2 dans C1 sans recouvrement.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Entrée

La première ligne de l'entrée contient la chaîne de caractères C1 qu'il faut analyser, la seconde la séquence C2 qu'il faut compter. Le tout est suivi d'un retour à la ligne.

Sortie

La sortie du programme indique le nombre maximum de fois que l'on peut retrouver la séquence C2 dans C1 sans recouvrement. La réponse sera suivie d'un retour à la ligne.

Exemples

Exemple 1

entrée : 

ABCDAAAABCD
AAAA

sortie : 

1

Exemple 2

entrée : 

AAAAAAAAAAAA
AAAA

sortie : 

3

Exemple 3

entrée : 

ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD
DCBA

sortie : 

0

Commentaires

Squelettes de codes : 

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* on recupere c1 et c2, les chaines de caractere fonctionnent comme les tableaux
en caml-light et OCaml : on accede a un element en i-eme position d'une chaine c
en utilisant c.[i] en OCaml ou en CamlLight, et a la taille de c en utilisant
string_length c en CamlLight ou String.length c en OCaml *)
let c1 = input_line stdin;;
let c2 = input_line stdin;;

(* fonction pour afficher votre solution *)
let affiche_solution i =
  print_int i;
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)
Source : https://www.france-ioi.org/