Battage – Épreuve régionale 2007

Niveau 4

ENONCE

Soient deux chaines de caractères s1 et s2. On appelle battage de s1 et s2 toute chaine s composée des caractères de s1 et s2, à condition que les caractères de s1 se retrouvent dans le même ordre dans s (et la même chose pour les caractères de s2). Un caractère de s appartient soit à s1, soit à s2, mais pas aux deux à la fois. Aussi, tous les caractères de s doivent être soit dans s1, soit dans s2.

CONTRAINTES

1 \<= length(s1) \<= 4000

1 \<= length(s2) \<= 4000

1 \<= length(s) \<= 8000

ENTREE

La première ligne de l'entrée contient la taille de la chaîne s1. La deuxième ligne contient la chaîne s1

La première ligne de l'entrée contient la taille de la chaîne s2. La deuxième ligne contient la chaîne s2

La première ligne de l'entrée contient la taille de la chaîne s. La deuxième ligne contient la chaîne s

SORTIE

La sortie contiendra 0 si s n'est pas un battage de s1 et s2, 1 dans le cas contraire.

Contraintes d'exécution

Utilisation mémoire maximum
70000 kilo-octets
Temps d'exécution maximum
1500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
1
a
1
b
2
ab
Exemple de sortie
1
Exemple d'entrée
3
aaa
3
bab
6
ababaa
Exemple de sortie
1
Exemple d'entrée
5
aabbc
4
bbaa
9
aabbabbca
Exemple de sortie
1