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 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..100. 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:
8 10010001100001001001001010010 00000111101111111110010 010000101001100 1111010100 0000111100000 1011 10111100011110110 001 00011011101101001001 1100001111000 000001 11 01010101010100001010001101 0111011011 01110000111010101 000101
Poprawną odpowiedzią jest wyjście:
00000111101111111110010001100001001001001010010 111101010000101001100 00001111000001011 10111100011110110 110000111100011011101101001001 0000011 0101010101010000101000110111011011 000101110000111010101
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 :