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:
9 1100001000101101101 111101011101010110 10010111110 0 11111000110001001100100010010 010100001011000011 01010110101001001000000001011 00110 0010111001 0 01000000000000111000111011 010110010010 10001000100 0001100001 111010011110001011001 110 101000000000010110011100 111011110101010101111
Poprawną odpowiedzią jest wyjście:
1111010111010101100001000101101101 10010111110 11111000110001001100100010010100001011000011 001101010110101001001000000001011 0010111001 01011001001000000000000111000111011 1000100010001100001 111010011110001011001 11101111010101010111101000000000010110011100
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 :