8. Sztring műveletek¶
Minimumkeresés¶
Mennyi a minimumkeresés időbonyolultsága?
Ha nem feltételezünk rendezettséget, akkor hogyan lehet javítani az algoritmus számítási idején?
Tegyük fel, hogy adott egy páros elemszámú tömbünk. Számítsuk ki ennek a minimumát és a maximumát!
Vizsgáljuk meg a külön-külön történő számításból adódó algoritmust és annak futási idejét!
Írjuk fel az előadásban javasolt algoritmus pszeudó kódját, és nézzük meg a működését az alábbi példát!
Feloszt eljárás¶
Osszuk fel az alábbi tömb elemeit az 50-es érték körül!
Mennyi cserére volt szükség az algoritmus végrehajtása során?
Mi a kapott \(q\) érték?
Mennyi volt a cserék során az \(i\) és \(j\) indexek különbségének maximuma?
Sztring műveletek¶
Konkatenálás¶
Írjuk fel a sztringek konkatenálásának egy lehetséges procedúrájának pszeudó kódját!
Adjunk egy példát, amin megnézhetjük az algoritmus működését!
Milyen a számítási ideje az algoritmusnak?
Részsztring törlése¶
Készítsünk egy procedúrát, amelyik szövegből egy adott részt képes törölni (kivágni)!
Vizsgáljuk meg a részsztring megadásának lehetséges módjait!
Írjuk fel a procedúra pszeudókódját!
Egészítsük ki hibaellenőrzéssel!
Részsztring keresése¶
Keressük meg a „kllm” szöveget a „ktlkkllzkllmzt” szövegben!
Egyeztessük a jelöléseket!
Használjuk hozzá a Brute force algoritmust!
Prefix és postfix¶
Készítsünk egy algoritmust, amelyik egy adott \(A\) alapsztringről meg tudja állapítani, hogy annak egy \(P\) sztring valódi prefixe/szuffixe-e!
Maximális border meghatározása¶
Készítsünk egy algoritmust, amely képes megkeresni egy szövegben a maximális border értékét! (\(b = ?\))
Becsüljük meg az algoritmus számítási idejét!
Vizsgáljuk meg az algoritmus működését a „
cabcxabbxacab” szöveg példáján keresztül!Mennyi a maximális border értéke?
Mennyi karakterösszehasonlításra volt szükség az algoritmus végrehajtása során?
A \(KÖV\) tömb számítása¶
Számítsuk ki a \(KÖV\) tömb értékét a „cdecdecd” sztring esetében!
\(i\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
\(p[i]\) |
c |
d |
e |
c |
d |
e |
c |
d |
|
\(KÖV[i]\) |
Hasonlóképpen vizsgáljuk meg az „
xyxzxxy” szöveget is!
Knuth-Morris-Pratt algoritmus (KMP)¶
A KMP algoritmus segítségével keressük meg a „
cdecd” szöveget az „edecdcdecdee” szövegben!Hasonlítsuk össze a szükséges számítási lépések számát a Brute force algoritmuséval!
\(i\) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
\(A[i]\) |
e |
d |
e |
c |
d |
c |
d |
e |
c |
d |
e |
e |
Nézzük meg a további példákat is!
alapsztring |
minta |
|---|---|
|
|
|
|
|
|