Zadanie : palin-2c
Zadanie

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.

Wejście

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.

Wyjście

Wyznaczone słowa dla wszystkich podanych na wejściu par słów.

Przykład

Dla danych podanych na wejściu:

7
110111010 00100111
101100110001010100100000 11010000010001001100111
010111011100101011110011001 0010011010111011001
11111000 01001110
0110001011000111010000 01001000110011
10000000111001000111010010000 0110000010110111101110111100
1001110110 01100

Poprawną odpowiedzią jest wyjście:

001001110111010
1101000001000100110011101100110001010100100000
0101110111001010111100110010011010111011001
111110001001110
010010001100110001011000111010000
011000001011011110111011110000000111001000111010010000
10011101100

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 :