program lzw_count; uses crt; const MAX=1000; { maximální počet úseků v LZW kódu } LMAX=1000000000; { maximálni délka textu } type lzw=record zaznamu: word; zaznamy: array[1..MAX] of record vaha: longint; pismeno: char; { #0/#1 = odkaz na předchozí část textu #1 = blok vzniklý rozdělením bloku } zacatek: longint; delka: longint; end; end; procedure vstup(var lzw0: lzw; var pismeno: char); { Načteme vstup - jenom samé nudné technické náležitosti ... } var c: char; i1,i2: longint; begin lzw0.zaznamu:=0; c:=readkey; while c<>'/' do begin case c of 'a'..'z': begin inc(lzw0.zaznamu); lzw0.zaznamy[lzw0.zaznamu].vaha:=1; lzw0.zaznamy[lzw0.zaznamu].pismeno:=c; lzw0.zaznamy[lzw0.zaznamu].delka:=1; end; '(': begin i1:=0; c:=readkey; repeat i1:=10*i1+ord(c)-ord('0'); c:=readkey; until c=','; i2:=0; c:=readkey; repeat i2:=10*i2+ord(c)-ord('0'); c:=readkey; until c=')'; inc(lzw0.zaznamu); lzw0.zaznamy[lzw0.zaznamu].vaha:=1; lzw0.zaznamy[lzw0.zaznamu].pismeno:=#0; lzw0.zaznamy[lzw0.zaznamu].zacatek:=i1; lzw0.zaznamy[lzw0.zaznamu].delka:=i2; end; end; c:=readkey; end; pismeno:=readkey; end; function redukce(var lzw1,lzw2: lzw; pismeno: char):longint; var nalezeno: longint; index2, odkud: word; index: word; delka: longint; begin nalezeno:=0; { Nejdříve odstraníme písmena na konci zakomprimovaného textu } while (lzw1.zaznamu>0) and (lzw1.zaznamy[lzw1.zaznamu].pismeno>#1) do begin if lzw1.zaznamy[lzw1.zaznamu].pismeno=pismeno then nalezeno:=nalezeno+lzw1.zaznamy[lzw1.zaznamu].vaha; dec(lzw1.zaznamu); end; redukce:=nalezeno; if lzw1.zaznamu=0 then begin lzw2.zaznamu:=0; exit end; { Najdeme souvislý podrozdělený úsek na konci textu } index2:=lzw1.zaznamu; while lzw1.zaznamy[index2].pismeno<>#0 do dec(index2); odkud:=index2; lzw1.zaznamy[lzw1.zaznamu+1].zacatek:=LMAX; { A přeneseme do nového kódu } index:=1; delka:=0; lzw2.zaznamu:=0; while indexlzw1.zaznamy[index2].delka then begin inc(lzw2.zaznamu); lzw2.zaznamy[lzw2.zaznamu].vaha:=lzw1.zaznamy[index].vaha+lzw1.zaznamy[index2].vaha; lzw2.zaznamy[lzw2.zaznamu].pismeno:=lzw1.zaznamy[index].pismeno; lzw2.zaznamy[lzw2.zaznamu].zacatek:=lzw1.zaznamy[index].zacatek; lzw2.zaznamy[lzw2.zaznamu].delka:=lzw1.zaznamy[index2].delka; delka:=delka+lzw2.zaznamy[lzw2.zaznamu].delka; lzw1.zaznamy[index].pismeno:=#1; lzw1.zaznamy[index].zacatek:=lzw1.zaznamy[index].zacatek+lzw1.zaznamy[index2].delka; lzw1.zaznamy[index].delka:=lzw1.zaznamy[index].delka-lzw1.zaznamy[index2].delka; inc(index2); continue; end; { Sem bychom se nikdy neměli dostat ! } end; { lzw1.zaznamy[lzw1.zaznamu+1].zacatek= ???? } end; var lzw1,lzw2: lzw; vyskytu: longint; pismeno:char; begin vstup(lzw1,pismeno); vyskytu:=0; while lzw1.zaznamu<>0 do begin vyskytu:=vyskytu+redukce(lzw1,lzw2,pismeno); if lzw2.zaznamu=0 then break; vyskytu:=vyskytu+redukce(lzw2,lzw1,pismeno); end; writeln('Písmeno ',pismeno,' se v textu vyskytuje ',vyskytu,'-krát.'); end.