moho = optimalis.
a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.
legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).
legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.
ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.
a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.
indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].
az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.
// bocs, ha ez esetleg duplan jelenne meg. majd kitoroltetem a modikkal. |