Demi-finale 2007, épreuve machine - Battage

DIFFICULTE

LIMITE DE MEMOIRE

70000 ko

LIMITE DE TEMPS

1500 ms

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.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

1
a
1
b
2
ab
en sortie ...
1

Exemple 2
en entrée ...

3
aaa
3
bab
6
ababaa
en sortie ...
1

Exemple 3
en entrée ...

5
aabbc
4
bbaa
9
aabbabbca
en sortie ...
1