Deklaratív programozás

A feladat

Jelöljük az m ≥ 0 hosszú u szót alkotó karaktersorozatot a következőképpen: u0 u1 ... um-1. Az u és v szavakat, amelyek hossza rendre m és n, h-átfedőnek nevezzük, ha h ≥ 1, és a következő feltételek mind teljesülnek: um-h = v0, um-h+1 = v1, ..., um-1 = vh-1. Ilyenkor azt is mondjuk, hogy az u a v-vel h-átfedésben van.

Legfeljebb k helyen átfedőnek vagy röviden max-k-átfedőnek nevezzük azokat a ts-beli ti és tj szavakat, amelyekhez van olyan h egész 1 ≤ h ≤ k mellett, hogy ti utolsó h karaktere megegyezik tj első h karakterével, azaz ti tj-vel h-átfedésben van.

Szóláncnak nevezzük a ts-beli szavak olyan sorozatát, amely ts első szavával kezdődik, és amelyben a szomszédos szavak max-k-átfedők. A szóláncban a ts bármely szava legfeljebb egyszer fordulhat elő. A szólánc akkor ér véget, ha nem folytatható max-k-átfedő szóval. Ha t egy szólánc, akkor szavainak jelölése: t0, t1, ..., ti, ... .

Egy szólánc összevont alakjának hívjuk azt a betűsorozatot, amelyet úgy kapunk, hogy a szavakat egymás mellé írjuk úgy, hogy az átfedő részeket csak egyszer írjuk le. Például a ["saska", "kacsa", "csapat"] szólánc összevont alakja "saskacsapat". Egy t szólánc ti szavának eltolási mértéke nem más mint az összevont alakban őt megelőző karakterek száma. A fenti példában "saska" eltolási mértéke 0, a "kacsa" illetve a "csapat" szavak esetén ez a szám 3 illetve 5.

A szóláncok között rendezést definiálunk. Egy s szólánc megelőzi a t szóláncot, ha

• van olyan i ≥ 0, hogy a két szólánc 0, 1, ..., i indexű szava megegyezik, de az i+1 indexű szavuk különbözik, továbbá vagy
• si és si+1 kevesebb helyen fedik át egymást, mint ti és ti+1, vagy
• az említett átfedési mértékek megegyeznek, de si+1 az ábécé szerint megelőzi a ti+1 szót.

Szóláncfának nevezzük a ts-beli szavakból előállítható, egymástól különböző összes szóláncot tartalmazó fát. A szóláncfa minden csúcsa egy számot és egy ts-beli szót tartalmaz. Minden csúcsnak nulla vagy több gyermeke van (a nulla gyermeket tartalmazó csúcsok a fa levelei). Egy csúcs gyermekeiben levő szavak páronként különböznek.

Ha a szóláncfa gyökerétől egy leveléig terjedő úton a csúcsok szavait sorozatba rendezzük, szóláncot kell kapnunk. Ha ezt az összes levélre elvégezzük, a ts-beli szavakból álló összes szóláncot meg kell kapnunk. Egy csúcsban levő szám az ott megadott szó eltolási mértéke.

A fentiek értelmében a szóláncfa gyökerében 0, valamint a ts első szava van.

Rendezettnek nevezzük a szóláncfát, ha a leveleit balról jobbra bejárva az oda vezető szóláncok a fent definiált rendezés szerint növekvő sorrendben követik egymást.

Írjon programot szolancfa néven, amely egy nem üres ts szólistából rendezett szóláncfát állít elő k maximális átfedéshossz mellett.

Példák

A ["saska", "kacsa", "csapat", "patko", "kovalyog"] szólistából k=3 mellett az alábbi, egyetlen szóláncot tartalmazó szóláncfa állítható elő:

saska(0)
   kacsa(3)
     csapat(5)
        patko(8)
           kovalyog(11)

Ebben a példában minden csúcsnak (a levelet kivéve) egy gyermeke van; a gyermeket beljebb kezdéssel jeleztük. A zárójelbe tett szám az eltolás mértéke: azt adja meg, hogy hány karakter előzi meg az adott szót a szóláncban. Például a patko szót a 8 karakter hosszú saskacsa füzér előzi meg.

A ["saska", "kacsa", "csapat", "patko", "kovalyog", "atletika", "kacat"] szólistából k=3 mellett az alábbi, hat szóláncot tartalmazó szóláncfa állítható elő:

saska(0)
    atletika(4)
          kacat(10)
          kacsa(10)
            csapat(12)
               patko(15)
                  kovalyog(18)
   kacat(3)
      atletika(6)
            kacsa(12)
              csapat(14)
                 patko(17)
                    kovalyog(20)
   kacsa(3)
       atletika(7)
             kacat(13)
     csapat(5)
         atletika(9)
               kacat(15)
        patko(8)
           kovalyog(11)

Itt a saska szónak három, az első két szóláncban az atletika, a negyedik és ötödik szóláncban a kacsa, az utolsó két szóláncban pedig a csapat szónak két-két gyermeke van. Az atletika szó például azért előzi meg a kacat és kacsa szavakat, mert rövidebb az átfedése a saska szóval, mint az utóbbi két szóé (és nem azért, mert előbb van az ábécében). A kacat és kacsa szavaknak egyforma az átfedése a saska, illetve az atletika szavakkal, ezért a felsorolás sorrendje az ábécét követi.

SML-specifikációk

Írjon SML-függvényt szolancfa néven, amely egy nem üres ts szólistából a k maximális átfedéshossz mellett rendezett szóláncfát állít elő.

(* szolancfa : int -> string list -> szolancfa
 * szolancfa k ts = a ts szólista szavaiból a k maximális átfedés mellett felépíthető
 *   rendezett szóláncfa (a rendezett szóláncfa definícióját lásd a feladatkiírásban)
 * PRE: a ts szólista nem üres
 *)

Az ábécé szerinti sorrend megegyezik a String.compare által meghatározott sorrenddel. Egy fs füzérlista rendezhető a Listsort.sort String.compare fs függvényalkalmazással.

Példák

- val t1 = szolancfa 2 ["ab","bc","cd"];
> val t1 = csucs(0, "ab", [csucs(1, "bc", [csucs(2, "cd", [])])]) : szolancfa

- val t2 = szolancfa 1 ["ab","bc","cd","abc"];
> val t2 = csucs(0, "ab", [csucs(1, "bc", [csucs(2, "cd", [])])]) : szolancfa

- val t3 = szolancfa 2 ["ab","bc","cd","abc"];
> val t3 =
    csucs(0, "ab",
          [csucs(1, "bc", [csucs(2, "cd", [])]),
           csucs(0, "abc",
                 [csucs(2, "cd", []), csucs(1, "bc", [csucs(2, "cd", [])])])]) : szolancfa

- val t4 = szolancfa 999999 ["apu","asztalos","alma","utas","anyu","satu","malom"];
> val t4 =
    csucs(0, "apu",
          [csucs(2, "utas",
                 [csucs(5, "satu", []),
                  csucs(4, "asztalos", [csucs(11, "satu", [])])])]) : szolancfa

- val t5 = szolancfa 2 ["aaa","aab","baa","aaaa"];
> val t5 =
    csucs(0, "aaa",
          [csucs(2, "aaaa",
                 [csucs(5, "aab", [csucs(7, "baa", [])]),
                  csucs(4, "aab", [csucs(6, "baa", [])])]),
           csucs(2, "aab",
                 [csucs(4, "baa",
                        [csucs(6, "aaaa", []), csucs(5, "aaaa", [])])]),
           csucs(1, "aaaa",
                 [csucs(4, "aab", [csucs(6, "baa", [])]),
                  csucs(3, "aab", [csucs(5, "baa", [])])]),
           csucs(1, "aab",
                 [csucs(3, "baa",
                        [csucs(5, "aaaa", []), csucs(4, "aaaa", [])])])]) : szolancfa

- val t6 = szolancfa 3 ["omlik","alma","ikra","atom","ragad"];
> val t6 =
    csucs(0, "omlik",
          [csucs(3, "ikra",
                 [csucs(6, "alma", [csucs(9, "atom", [])]),
                  csucs(6, "atom", []), csucs(5, "ragad", [])])]) : szolancfa

Prolog-specifikációk

Írjon Prolog-eljárást szolancfa/3 néven, amely egy nem üres L1 szólistából a K maximális átfedéshossz mellett rendezett szóláncfát állít elő.

% :- type szo          == atom.
% :- type eltolas      == int.
% :- type atfedeshossz == int.
% :- type szolista     == list(szo).
% :- type szolancfa    ---> csucs(eltolas,szo,list(szolancfa)).
% :- pred szolancfa(szolista::in, atfedeshossz::in, szolancfa::out).

% szolancfa(K,L1,F), ahol az F az L1 szólista szavaiból a K maximális átfedés mellett felépíthető
%   rendezett szóláncfa (a rendezett szóláncfa definícióját lásd a feladatkiírásban)
% PRE: az L1 szólista nem üres

Az ábécé szerinti sorrend megegyezik a '@<'/2 eljárás által megállapított sorrenddel. Egy L1 lista rendezhető a sort(L1,L1S) hívással. (Ez ugyan összevonja az azonos elemeket, de ez nem baj, ha az L1-ben nincsenek azonos elemek.)

Példák

| ?- szolancfa(2,[ab,bc,cd],F).
F = csucs(0,ab,[csucs(1,bc,[csucs(2,cd,[])])]) ? ;
no

| ?- szolancfa(1,[ab,bc,cd,abc],F).
F = csucs(0,ab,[csucs(1,bc,[csucs(2,cd,[])])]) ? ;
no

| ?- szolancfa(2,[ab,bc,cd,abc],F).
F = csucs(0,ab,
          [csucs(1,bc,[csucs(2,cd,[])]),
           csucs(0,abc,
                 [csucs(2,cd,[]),csucs(1,bc,[csucs(2,cd,[])])])]) ? ;
no

| ?- szolancfa(999999, [apu,asztalos,alma,utas,anyu,satu,malom], F).
F = csucs(0,apu,
          [csucs(2,utas,
                 [csucs(5,satu,[]),
                  csucs(4,asztalos,[csucs(11,satu,[])])])]) ? ;
no

| ?- szolancfa(2, [aaa,aab,baa,aaaa], F).
F = csucs(0,aaa,
          [csucs(2,aaaa,
                 [csucs(5,aab,[csucs(7,baa,[])]),
                  csucs(4,aab,[csucs(6,baa,[])])]),
           csucs(2,aab,
                 [csucs(4,baa,
                        [csucs(6,aaaa,[]),csucs(5,aaaa,[])])]),
           csucs(1,aaaa,
                 [csucs(4,aab,[csucs(6,baa,[])]),
                  csucs(3,aab,[csucs(5,baa,[])])]),
           csucs(1,aab,
                 [csucs(3,baa,
                        [csucs(5,aaaa,[]),csucs(4,aaaa,[])])])]) ? ;
no                                                          
                                                              
| ?- szolancfa(3,[omlik,alma,ikra,atom,ragad],F).            
F = csucs(0,omlik,
          [csucs(3,ikra,
                 [csucs(6,alma,[csucs(9,atom,[])]),
                  csucs(6,atom,[]),csucs(5,ragad,[])])]) ? ;
no

Megjegyzés

Tudnivalók a beadásról

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.