8865번 - Prawie jak LCS 다국어

Podciągiem ciągu zerojedynkowego nazywamy ciąg powstały poprzez wybranie pewnej liczby elementów z pierwotnego ciągu. Przykładowo, wszystkie niepuste podciągi ciągu 010 to 0, 1, 00, 01, 10, 010. Wspólnym podciągiem dwóch ciągów, nazywamy ciąg, który jest podciągiem w obu ciągach. Przykładowo, wszystkie niepuste wspólne podciągi ciągów: 101 i 011 to: 0, 1, 01, 11. Dla dwóch ciągów C₁ i C₂ przez LCS(C₁,C₂) oznaczamy jeden z najdłuższych podciągów C₁ i C₂, a przez |LCS(C₁,C₂)| jest długość. Przykładowo, LCS(101,011) to 11 lub 01 i |LCS(101,011)| = 2.

Ulubionym przedmiotem Władka, studenta informatyki na Uniwersytecie Wrocławskim, są Algorytmy Tekstowe. Na pierwszym wykładzie, Władek dowiedział się (a raczej przypomniał sobie) o problemie obliczania LCS dla dwóch ciągów. Oprócz klasycznego algorytmu opartego na programowaniu dynamicznym, na zajęciach zostało zaprezentowanych wiele innych metod na rozwiązanie tego problemu. Niestety, wszystkie algorytmy dla najgorszego przypadku nie działały dużo szybciej niż najprostszy algorytm, który Władek znał już od dawna. Zawiedziony przedstawionymi wynikami, Władek postanowił wymyślić nowy, szybki algorytm, który dla dwóch zerojedynkowych ciągów C₁, C₂ znajdowałby jakieś dobre przybliżenie LCS. Po wielu dniach udało się! Algorytm Władka zawsze znajduje podciąg o długości większej niż 0.5|LCS(C₁,C₂)|. Czy umiesz powtórzyć jego osiągnięcie?

W pierwszej linii znajdują się dwie, oddzielone pojedynczym odstępem liczby całkowite n i m (1<=n,m<=100000). W drugiej linii znajduje się binarny, n-elementowy ciąg C₁. W trzeciej linii znajduje się binarny, m-elementowy ciąg C₂.

W pierwszej linii Twój program powinien wypisać jedną liczbę k - długość znalezionego wspólnego podciągu C₁ i C₂. W drugiej linii Twój program powinien wypisać ten podciąg. Odpowiedź uznana zostanie za poprawną jeżeli 2k > |LCS(C₁,C₂)|. Możesz założyć, że |LCS(C₁,C₂)|>0.

Wszystkie, poprawne podciągi odpowiedniej długości to: 100, 000, 1000.