Szkolna Liga Zadaniowa w PLO II

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:

6
01101100 01
1001011100100111110 111010011101111
001011011110 101
101110000111011000010010111101 1101110101
11000000000 00
1111101011 01010010

Poprawną odpowiedzią jest wyjście:

01101100
100101110010011111010011101111
001011011110
101110000111011000010010111101110101
11000000000
111110101101010010

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 :