Najveći zajednički podniz
Opis zadatka:
Data su dva niza znakova, u kojima svaki znak predstavlja jedno slovo engleske abecede.
Prvi niz ima M članova, a drugi N članova. Potrebno je napisati program
koji će nalaziti dužinu najvećeg zajedničkog podniza datih nizova. Podniz nastaje biranjem
proizvoljnih članova niza (ne nužno susjednih), ali tako da njihovi indeksi rastu. Tako, na
primjer, ako imamo niz
{a,a,b,c,d,c,e},
neki od njegovih podnizova su
{a,a,b,d,e},
{b,c,d,c},
{c,c,e}, dok niz
{a,a,c,b} ne smatramo podnizom datog niza.
Ulazna datoteka:
U prvoj liniji tekstualne datoteke PODNIZ.IN nalazi se prirodan broj
M (M <= 1000), koji predstavlja broj članova prvog niza. U svakoj
od slijedećih M linija nalazi se po jedan znak (slovo) koji predstavlja odgovarajući
element prvog niza. Nakon toga, u narednoj liniji nalazi se prirodan broj
N (N <= 1000), koji predstavlja broj članova drugog niza, nakon
čega se u svakoj od slijedećih N linija nalazi odgovarajući element drugog niza.
Datoteka će se nalaziti u tekućem direktoriju.
Izlazna datoteka:
U tekstualnu datoteku PODNIZ.OUT potrebno je (u prvoj liniji) upisati broj
koji predstavlja dužinu najvećeg zajedničkog podniza za date nizove.
Nikakva obrazloženja nije potrebno pisati u izlaznu datoteku.
Vremensko ograničenje:
Za svaki testni primjer program treba da ponudi rješenje za najviše 20 sekundi.
Primjeri:
PODNIZ.IN
5
a
b
c
d
e
4
a
c
e
e
PODNIZ.OUT
3
Objašnjenje: najveći zajednički podniz je {a,c,e}.
[Rješenje (Pascal)]
[Rješenje (C++)]