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:
8 01011111011111000101011 1101011001000010000101 000010001111101010111101 0000100011101 011 1 000000010101010011111 0011101001011100101 11100011110101110101 01101000110 10111001111010100000011111 10111000000110001100 0010001111110010 1101100011 11111101110001 01110
Poprawną odpowiedzią jest wyjście:
11010110010000100001011111011111000101011 0000100011111010101111010000100011101 011 0000000101010100111110011101001011100101 11100011110101110101101000110 101110011110101000000111110111000000110001100 00100011111100101101100011 11111101110001
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 :