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:
10 01101100100010111 1111110 101100100111000001011110 00110100111 01101110110 111 001011101110101000111 001101000000010010000 000 100 11 10 1101101110011111000011 01100 001 0 0000010010 110000101 0011100001 10011001
Poprawną odpowiedzią jest wyjście:
011011001000101111110 1011001001110000010111100110100111 01101110110 0011010000000100100001011101110101000111 1000 110 110110111001111100001100 001 0000010010110000101 100110011100001
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 :