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 10101010010000011111111110111 0 01010000100100000100101011 11010 101111011111011100100010000 00100000111011111100011111 11111011110110010011001000111 1100100010100110111000000 0110111111110010000000 000 10101001111000010000101 11101010001001 1110010000011100011001 0000000110111110011001 0001110 1 00100110001000101001000 001110001111101011
Poprawną odpowiedzią jest wyjście:
10101010010000011111111110111 1101010000100100000100101011 1011110111110111001000100000111011111100011111 1111101111011001001100100011100100010100110111000000 0110111111110010000000 101010011110000100001011101010001001 0000000110111110011001110010000011100011001 0001110 001001100010001010010001110001111101011
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 :