Dana jest lista par słów składających się ze znaków 0 i 1. W każdej parze drugie ze słów ma długość nie większą od długości pierwszego słowa.
Prefiksem słowa nazywamy dowolny początkowy fragment tego słowa. Podobnie sufiksem słowa nazywamy dowolny końcowy fragment słowa.
Mając daną parę słów a i b, można znaleźć najkrótsze słowo c, które będzie zawierać w sobie oba dane słowa a i b.
Przykłady:
a=10011101, b=111 c:=a, ponieważ a zawiera w sobie słowo b
AAAAAAAA
a=10011101, b=1100 c:=110011101, trzyznakowy sufiks słowa b jest taki
BBBB sam jak trzyznakowy prefiks słowa a
AAAAAAAA
a=10011101, b=1010 c:=100111010, trzyznakowy prefiks słowa b jest taki
BBBB sam jak trzyznakowy sufiks słowa a
AAAAAAAA
a=10011101, b=000 c:=10011101000, słowo c jest wynikiem sklejenia słowa
BBB a ze słowem b
Dla dowolnej pary słów a i b możemy w dosyć łatwy sposób wyznaczyć najkrótsze słowo c zawierające oba słowa a i b stosując następujący algorytm:
1. Jeżeli b zawiera się w a to c:=a
2. W p.p.:
a) suf_b - długość najdłuższego sufiksu słowa b, który jest prefiksem a
b) pre_b - długość najdłuższego prefiksu słowa b, który jest sufiksem a
c) jeśli suf_b>pre_b, to słowo c tworzymy zgodnie z przykładami w treści
zadania umieszczając słowo b przed słowem a
c) w p.p. umieszczamy słowo a przed słowem b
Dla każdej pary słów wypisz słowo otrzymane opisanym powyżej algorytmem.
Pierwszy wiersz wejścia zawiera liczbę całkowitą z zakresu 1..1000. W każdym z kolejnych n wierszy zapisano parę słów zerojedynkowych o maksymalnej długości 30 znaków każde.
Wyznaczone słowa dla wszystkich podanych na wejściu par słów.
Dla danych podanych na wejściu:
9 101011111111111110010011001 1 1011110010101000111001001101 010001010110100010111101000 0110110110111111001101 0 1110001111010010 0101010101001110 01101 00000 10010010100010101011 111100000011110 1111111011110101101001100011 111110100110101000011011110 1111 101 1110100100 0000100
Poprawną odpowiedzią jest wyjście:
101011111111111110010011001 10111100101010001110010011010001010110100010111101000 0110110110111111001101 0101010101001110001111010010 000001101 100100101000101010111100000011110 11111110111101011010011000111110100110101000011011110 111101 111010010000100
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath string Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :