Najdłuższy wspólny podciąg

02.10.2010 - Marcin Oczeretko
TrudnośćTrudność

Zadanie A

    Czy potrafisz szybko odpowiadać na wiele pytań o najdłuższy wspólny podciąg pary dowolnych prefiksów wyrazów $ A $ i $ B $?

Wejście

    Pierwszy wiersz wejścia zawiera ciąg znaków (małe i duże litery alfabetu łacińskiego oraz cyfry $ 0-9 $) będący wyrazem $ A $, o którym wiemy, że jego długość nie przekracza $ 2010 $.

    W wierszu drugim znajduje się ciąg liter będący słowem $ B $, który również spełnia wszystkie powyższe ograniczenia.

    Trzeci wiersz zawiera jedną liczbę naturalną $ n $.

    W każdej z kolejnych $ n $ linijek znajdują się takie dwie nieujemne liczby całkowite $ a_i $ i $ b_i $, że długość $ A $ jest nie większa niż $ a_i $, a długość $ B $ nie większa niż $ b_i $.

Wyjście

    Dla każdej pary liczb $ a_i $ i $ b_i $ należy wypisać najdłuższy podciąg wyrazów $ A_{a_i} $ i $ B_{b_i} $ (gdzie $ K_i $ to wyraz będący $ i $ pierwszymi literkami wyrazu $ K $). Jeśli istnieje wiele podciągów o największej długości, to wypisz dowolny z nich. Jeśli LCS będzie miał długość 0 (czyli będzie słowem pustym), to zamiast niego wypisz znak !.

Przykład

    Dla wejścia:

cdcddbdadbcdbdbddada
ddcdddaaccd
10
5 5
18 7
3 8
10 5
1 4
14 7
9 1
12 6
12 9
1 1

    Poprawnym wyjściem będzie:

dcdd
ddcddda
dc
dddd
c
dcddda
d
ddddd
dcdddac
!

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Zadanie B

    W tym zadaniu należy jedynie znaleźć długość LCS dla dwóch podanych na wejściu wyrazów. Limit pamięci jest jednakże niewielki, dlatego postaraj się ograniczyć jej zużycie.

Wejście

    Wejście składa się z dwóch wierszy. W każdym znajduje się niepusty ciąg znaków (małe litery alfabetu łacińskiego) o długości mniejszej niż $ 4001 $. Pierwszy wiersz zawiera wyraz $ A $, drugi - $ B $.

Wyjście

    Należy wypisać jedną nieujemną liczbę całkowitą równą długości najdłuższego wspólnego podciągu wyrazów $ A $ i $ B $.

Przykład

    Dla wejścia:

dcbbaacbda
dacddaadaabbcbb

    Poprawnym wyjściem będzie:

6

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

5
Twoja ocena: Brak Ocena: 5 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com