Šeštadieninė informatikos olimpiadininkų mokykla

Kartais išsiuntus labai daug galimų problemos sprendimo variantų, darosi sunku sekti kokie pakeitimai kaip įtakojo galutinį programos pasirodymą. siuntimas - klaida teste, siuntimas - klaida teste - o ką aš pakeičiau?

Į tokius klausimus padeda atsakyti specialios programos, atliekančios failų skirtumų analizę. Pavyzdžiui, jeigu turime du sprendimus:

#include      \<cstdio>
int main(int argc, char argv) {
    int N;
    scanf("\%d", &N);
    if (N == 0) printf("\%d", 0);
    else printf("\%.2f", 5.0 / N);
    return 0;
}

#include      \<cstdio>
int main(int argc, char **argv) {
    int N;
    scanf("\%d", &N);
    if (N < 0) printf("\%.2f", -5.0 / N);
    else printf("\%.2f", 5.0 / N);
    return 0;
}

Galime pasinaudoti standartine UNIX program diff (tie, kas nori pasibandyti vizualius multiplatforminius įrankius, gali pasidomėti - meld, kdiff3, vimdiff ir t.t.) ir taip sužinoti kokie pakeitimai buvo padaryti:

\$ diff 37.cpp 84.cpp
5c5
\<       if (N == 0) printf("\%d", 0);
---
>       if (N < 0) printf("\%.2f", -5.0 / N);

Ir ką mes sužinojome? Na diff pasakė, kad tarp šių siuntimų buvo vienintelis pakeitimas, t.y. 37.cpp 5 eilutė buvo pašalinta ir pakeista 5 84.cpp eilute. Tad norint išspręsti uždavinį, kuris klausia kokia bus išraiškos absoliuti (be minuso) reikšmė, reikia siųsti programą:

#include      \<cstdio>
int main(int argc, char **argv) {
    int N;
    scanf("\%d", &N);
    if (N == 0) printf("\%d", 0);
    else if (N < 0) printf("\%.2f", -5.0 / N);
    else printf("\%.2f", 5.0 / N);
    return 0;
}

Skirtumų ieškančios programos savo darbą atlieka trimis etapais. Pirmajame etape jos kiekvieną failų F1 ir F2 eilutę perleidžia per maišos funkciją, taip eilutes supaprastinant ir palengvinant jų lyginimą (pvz.: failą F1 galėtų atitikti - 'abcdefgh', o F2 - 'abcdzfgh'). Antrojo etapo metu atliekamas algoritmas, kuris pasako didžiausią bendrą failų eilučių poaibį S. Trečiajame etape, skirtumų ieškančios programos, atlieka modifikuotą sąlajos algoritmą, kuris lygina failų F1 ir F2 eilutes su S ir pažymi, kurios eilutės buvo išmestos, o kurios įdėtos.

Jūsų užduotis bus atlikti antrąją programos veikimo dalį. Jums bus duotos dvi simbolinės eilutės, kurių pirmoji atitiks failo F1 eilutes perleistas per maišos funkciją, o antroji failo F2. Taip pat žinoma, kad maišos funkcija, naudota konvertuojant eilutes, vienai eilutei grąžina vieną lotynišką raidę.

Pradiniai duomenys

2 simbolinės eilutės (pateiktos skirtingose eilutėse), sudarytos iš lotyniškų raidžių. Kiekvienos eilutės ilgis yra mažesnis už .

Rezultatai

Maksimalus bendras duotų eilučių poaibis.

Pavyzdžiai

abcdefgh
abcdzfgh

abcdfgh