Battage – Regional event 2007

Level 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.

Runtime constraints

Maximum memory usage
70000 kilobytes
Maximum execution time
1500 milliseconds

Input/output samples

Sample input
1
a
1
b
2
ab
Sample output
1
Sample input
3
aaa
3
bab
6
ababaa
Sample output
1
Sample input
5
aabbc
4
bbaa
9
aabbabbca
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.