Инкременталност

Увод

Поред одсецања, инкременталност је још једна елементарна техника којом се може снизити временска сложеност алгоритма. Најчешће, висока временска сложеност алгоритма крије се у израчунавању истих ствари већи број пута. Дакле, ако желимо да убрзамо наше решење потребно је да нађемо неки начин којим ћемо елиминисати вишеструко израчунавање истих ствари.

Једна техника којом се то може постићи је управо инкременталност. Решење или израчунавање тражене величине ћемо звати инкременталним ако важи следеће:

Овакав опис инкременталности не открива потпуни смисао онога што желимо да постигнемо, па ћемо покушати да објаснимо идеју на једноставном примеру одређивања парцијалних збирова (збирова префикса) елемената неког низа. На пример, ако је дат низ $$1, 2, 3, 4, 5$$ његови парцијални збирови су редом $$0, 1, 3, 6, 10, 15$$. Веома једноставно се примећује да се израчунавање наредног парцијалног збира не мора вршити сабирањем свих елемената од почетка, већ се може добити сабирањем претходног парцијалног збира са текућим елементом низа (на пример, збир $1 + 2 + 3 + 4 = 10$, се добија сабирањем претходног збира $1 + 2 + 3 = 6$ и текућег елемента $4$). Ако збир првих $k$ елемената означимо са $Z_k$ и елементе низа са $a_k$, тада важи да је $$Z_k = \begin{cases} 0, \quad \text{за } k = 0\\ Z_{k-1} + a_k \quad \text{за } 1 \le k \le n \end{cases}$$ Овим смо добили серију бројева у којој се наредни елемент израчунава на осно- ву претходног (или неколико претходних). За такве серије кажемо да су рекурентне серије. Сваки наредни члан се израчунава у сложености $O(1)$, па се израчунавање свих парцијалних збирова низа дужине $n$ врши у сложености $O(n)$. Када би се сваки парцијални збир рачунао сабирањем елемената низа из почетка, тада би израчунавање $k$-тог збира било сложености $O(k)$, а израчунавање свих збирова сложености $O(n^2)$.

Груба подела проблема на које се може применити инкременталност може се извршити на следећи начин:

• Инкременталност збира и производа - Најчешће се своди на инкрементално одређивање парцијалних збирова или производа и њихову примену у израчунавању решења целог проблема.
• Инкременталност минимума и максимума - Најчешће се своди на инкрементално одређивање максимума или минимума префикса или суфикса и њихову примену у израчунавању решења целог проблема.
• Покретни прозор - Најчешће се своди на израчунавање статистика на подсегментима датог скупа података. Убрзање се може добити тако што приликом преласка на наредни подсегмент само ажурирамо раније познато решење за претходни сегмент, уместо да рачунамо све испочетка за нови сегмент.
• Збирови префикса и суфикса - Најчешће представља примену инкременталности и препроцесирање, тј. промену репрезентације улазних података да бисмо тиме убрзали решење полазног проблема.

Принцип инкременталности је у тесној вези са индуктивно/рекурзивном конструкцијом алгоритама и лежи у основи великог броја основних алгоритама. Већ само израчунавање збира свих елемената низа заправо почива на постепеном, инкременталном израчунавању збирова префикса, све док се не израчуна збир свих елемената низа. Слично је и са израчунавањем минумума, максимума, линеарном претрагом и другим фун- даменталним алгоритмима. У свим овим примерима крећемо од неке почетне вредности у низу резултата, а затим наредну вредност у том низу израчунавамо на основу претходне или неколико претходних, што директ- но одговара индуктивном поступку израчунавања. Добијања наредних резултата на основу претходних није идеја карактеристична само за индуктивност, већ се користи и у напреднијим техникама за конструкцију алгоритама, попут динамичког програмирања навише, о чему ће више речи бити касније.

Једноставнијим речима инкременталност се може окарактерисати на следећи начин:

У пракси, уколико смо нешто већ израчунали, не треба то исто да израчунавамо поново испочетка, већ треба само да искористимо ту раније познату вредност и прилагодимо је траженом резултату. Прецизније, треба дефинисати образац којим ћемо постојеће решење проширити следећим елементом са улаза.

На крају, треба нагласити да се инкременталност и одсецање морају посматрати као две технике које се допуњују и често комбинују у пракси. И једна и друга техника леже у основи великог броја сложенијих алгоритама. Правилно разумевање и разликовање основних техника за конструкцију алгоритама је кључно за успешно разумевање напреднијих техника за конструкцију алгоритама.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Сваког дана током неког периода на банковни рачун је вршена тачно једна трансакција (уплата или исплата новца). Ако је почетно стање на рачуну нула, напиши програм који одређује највеће стање на рачуну током тог периода.

Улаз: Са стандардног улаза се уноси број $n$ ($1 \le n \le 100000$), а затим и $n$ целих бројева (сваки у посебној линији) који представљају трансакције (позитиван број означава уплату, а негативан исплату).

Излаз: На стандардни излаз исписати један цео број који представља највеће стање на рачуну у неком тре- нутку.

Решење

Задатак врло лако можемо да решимо тако што ћемо за сваку трансакцију да рачунамо стање на рачуну почевши од прве трансакције. Иако идејно лако, наивно решење није временски ефикасно.

static int zad1(int[] transakcije)
{
    int maxStanje = 0;
    for (int i = 0; i < transakcije.Length; i++)
    {
        int stanjeNaDanI = 0;
        for (int j = 0; j <= i; j++) 
            stanjeNaDanI += transakcije[j];
        if (stanjeNaDanI > maxStanje)
            maxStanje = stanjeNaDanI;
    }
    return maxStanje;
}

Разлог неефикасности наивног решења су линије обележене жутом бојом у функцији zad1(). Лако се може уочити да са сваком следећом трансакцијом у приказаном решењу испочетка рачунамо збир трансакција од почетка. Такође, лако се уочава да са сваком следећом трансакцијом заправо треба да променимо текуће стање управо за износ те трансакције. Овако измењено решење је приказано у наставку и инкрементално израчунавање је обележено жутом бојом.

static int zad1_inkrementalno(int[] transakcije)
{
    int tekuceStanje = 0;
    int maxStanje = 0;
    for (int i = 0; i < transakcije.Length; i++)
    {
        tekuceStanje += transakcije[i];
        if (tekuceStanje > maxStanje)
            maxStanje = tekuceStanje;
    }
    return maxStanje;
}

Временска сложеност наивног алгоритма је квадратна, а инкременталног алгоритма је линеарна. Приметимо да поред инкременталног рачунања парцијалних збирова низа, тј. текућег стања, такође инкрементално израчунавамо и максимум.

Задатак 2

Напиши програм који за дати низ целих бројева одређује број непразних сегмената узастопних елемената низа чији је збир једнак датом броју.

Улаз: Са стандардног улаза се у првој линији уноси тражена вредност збира $х$ (цео број $−10000$ и $10000$), затим, у наредној линији димензија низа $n$ ($3 \le n \le 50000$) и затим у $n$ наредних линија елементи низа (цели бројеви између $-100$ и $100$).

Излаз: На стандардни излаз испиши број сегмената чији је збир једнак $х$.

Решење

Решење које директно следи из текста задатка је лако конструисати. Потребно је да одредимо збирове свих могућих сегмената и да пребројимо колико међу тим сегментима има оних чији је збир једнак баш $х$. Дакле, потребно је одредимо све могуће почетке ($i$) и крајеве ($j$) сегмената ($0 \le i \le j < n$) и да за тако дефинисан сегмент одредимо његов збир $z = \sum_{k = i}^{j} a_k$. Ако је збир једнак траженом, увећаћемо бројач. Описано решење је у наставку:

static int zad2_naivno(int[] niz, int x)
{
    int brSegmenata = 0;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int zbir = 0;
            for (int k = i; k <= j; k++)
                zbir = zbir + niz[k];
            if (zbir == x)
                brSegmenata++;
        }
    }
    return brSegmenata;
}

Наивно решење је неефикасно, јер изнова и изнова рачунамо збирове сегмената. Проблематични део кода је обележен жутом бојом у претходном решењу.

Решење можемо да убрзамо тако што ћемо збирове сегмената рачунати инкрементално. Инкременталност се може лако уочити. Увећавањем бројача $j$ за $1$ ми заправо у наш сегмент додајемо следећи елемент низа. Збир тако проширеног сегмента биће једнак збиру полазног сегмента увећаном за вредност елемента на позицији $ј$ у низу. Дакле, нема потребе да рачунамо збир тако проширеног сегмента испочетка, већ можемо да искористимо стару вредност збира. Инкрементално решење је у наставку:

static int zad2_inkrementalno(int[] niz, int x)
{
    int brSegmenata = 0;
    for (int i = 0; i < niz.Length; i++)
    {
        int tekuciZbir = 0;
        for (int j = i; j < niz.Length; j++)
        {
            tekuciZbir = tekuciZbir + niz[j];
            if (tekuciZbir == x)
                brSegmenata++;
        }
    }
    return brSegmenata;
}

Инкрементално израчунавање збира сегмента је обележено жутом бојом у приказаном решењу. Временска сложеност наивног решења је $O(n^3)$, док је временска сложеност инкременталног решења $O(n^2)$

Задатак 3

Једна финансијска компанија тргује на берзи током $n$ дана. Позната је њена зарада током сваког дана (она може бити и негативна, ако је комапнија тог дана трговала неповољно). Одредити најмањи број узастопних дана у ком је збир зарада компаније бар $k$.

Улаз: Са стандардног улаза се уноси цео број $k$ ($1 \le k \le 10^5$ ), а затим број дана $n$ ($1 \le n \le 10^5$) и у наредном реду зарада током $n$ дана (цели бројеви између и $−2000$ и $2000$).

Излаз: На стандардни излаз исписати тражени најмањи број дана или $0$ ако компанија током тих n дана никада није остварила збирну зараду $k$.

Решење

Као и у претходном задатку одредићемо збирове свих могућих сегмената и затим ћемо од тих сегмената изабрати најкраћи чији је збир барем $k$. У наставку је наивно решење са обележеним проблематичним делом. Као и у претходном задатку, збирове сегмената рачунамо увек испочетка.

static int zad3_naivno(int[] niz, int x)
{
    int minDuzina = int.MaxValue;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int zbir = 0;
            for (int k = i; k <= j; k++)
                zbir = zbir + niz[k];
            if (zbir >= x && (j - i + 1)< minDuzina)
            {
                minDuzina = j - i + 1;
            }
        }
    }
    return minDuzina == int.MaxValue ? 0 : minDuzina;
}

На исти начин и са истим аргументима као и у претходном задатку, можемо прећи на инрементално израчунавање збирова сегмената. Поред тога, можемо инкрементално да испитујемо и дужину најкраћег сегмента чији је збир барем $k$. У наставку је приказано и обележено инкрементално решење задатка.

static int zad3_inkrementalno(int[] niz, int x)
{
    int minDuzina = int.MaxValue;
    for (int i = 0; i < niz.Length; i++)
    {
        int tekuciZbir = 0;
        for (int j = i; j < niz.Length && (j - i + 1) < minDuzina; j++)
        {
            tekuciZbir += niz[j];
            if (tekuciZbir >= x && (j - i + 1) < minDuzina)
            {
                minDuzina = j - i + 1;
            }
        }
    }
    return minDuzina == int.MaxValue ? 0 : minDuzina;
}

Временске сложености оба решење су идентичне као у претходном задатку.

Задатак 4

У једној улици која иде ка реци налазе се разне куће и зграде. Инвеститор бира локацију на којој би изградио вишеспратницу, такву да се са њеног последњег спрата види река. Зато она мора бити виша или бар једна- ке висине од свих постојећих зграда од одабране локације до краја улице. Напиши програм који за сваку локацију у тој улици одређује минималну висину нове вишеспратнице.

Улаз: У првој линији стандардног улаза налази се природан број $n$ ($1 \le n \le 50000$). У следећих $n$ линија налазесе редом висине свих зграда и кућа од почетка до краја улице.

Излаз: На стандардном излазу приказати $n$ бројева (сваки у посебном реду) који приказују тражене висине.

Решење

Наивно, потребно је да за сваку позицију у низу резултата одредимо максимум свих елемената иза те позиције у полазном низу. Описани поступак је приказан у наставку:

static int[] zad4_naivno(int[] niz)
{
    int[] rezultat = new int[niz.Length];
    for (int i = niz.Length - 1; i >= 0; i--)
    {
        int max = niz[i];
        for (int j = i; j < niz.Length; j++)
        {
            if (niz[j] > max)
                max = niz[j];
        }
        rezultat[i] = max;
    }
    return rezultat;
}

Очигледно је да нема потребе да изнова и изнова испочетка рачунамо максимуме суфикса низа. Уместо тога, много је ефикасније да максимум суфикса низа рачунамо инкрементално почевши од последње позиције у полазном низу. Јасно је да ће тражена висина зграде у низу резултата бити управо једнака максимуму суфикса низа. Инрекемнтално решење је у наставку:

static int[] zad4_inkrementalno(int[] niz)
{
    int[] rezultat = new int[niz.Length];
    int tekuciMax = niz[niz.Length - 1];
    for (int i = niz.Length - 1; i >= 0; i--)
    {
        if (tekuciMax < niz[i])
            tekuciMax = niz[i];
        rezultat[i] = tekuciMax;
    }
    return rezultat;
}

Као и до сада, у наивном решењу је обележен узрок неефикасности, док је у ефикасном решењу обележено инкрементално израчунавање којим снижавамо временску сложеност решења. Временска сложеност наивног решења је квадратна, а временска сложеност инкременталног решења је линеарна.

Задатак 5

У низу различитих целих бројева нађи дужину најдужег сегмента (који чине узастопни елементи низа) који садржи бројеве који се могу уредити у низ узастопних целих бројева.

Улаз: У првој линији стандардног улаза уноси се број елемената низа $n$ ($1 \le n \le 10000$), а затим у следећих $n$ линија налазе се редом елементи низа.

Излаз: На стандардном излазу приказати дужину најдужег сегмента чији се елементи могу уредити у низ узастопних целих бројева.

Решење

Увек крећемо од наивне идеје. Наивно, могли бисмо као и до сада да испитујемо све могуће сегменте. Дакле, у двострукој петљи ћемо фиксирати почетак ($i$) и крај сегмента ($j$) и потребно је само још да испитамо да ли тај сегмент испуњава дати услов, тј. да ли се може уредити у узастопни низ целих бројева.

Очигледна идеја би била да сортирамо дати сегмент и да затим анализом суседних елемената проверимо да ли је сачињен од узастопних елемената. Проблем са оваквим приступом је у томе што захтева изузетно велики број сортирања за које знамо да нису ефикасне операције. Овакво решење нећемо имплементирати нити детаљније разматрати.

Уместо тога, можемо да искористимо поставку задатка. Из поставке задатка знамо да је наш низ сачињен од различитих елемената, тј. нема дупликата. Знајући то, можемо да утврдимо да ли сегмент испуњава услове без сортирања. Потребно је да израчунамо опсег вредности у сегменту, односно да нађемо разлику највећег и најмањег елемента у сегменту. Ако је та разлика једнака дужини сегмента, онда је очигледно да такав сегмент можемо преуредити у растући низ узастопних бројева. Решење које користи ову идеју је у наставку.

static bool uzastopniRastuci(int[] niz, int i, int j)
{
    int min = niz[0];
    int max = niz[0];
    for (int k = i; k <= j; k++)
    {
        if (niz[k] < min)
            min = niz[k];
        if (niz[k] > max)
            max = niz[k];
    }
    return (max - min) == (j - i);
}
static int zad5_naivno(int[] niz)
{
    int maxDuzine = -1;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int duzinaSegmenta = j - i + 1;
            if (uzastopniRastuci(niz, i, j)  &&  duzinaSegmenta > maxDuzine)
            {
                maxDuzine = duzinaSegmenta;
            }
        }
    }
    return maxDuzine;
}

У приказаном решењу посебну пажњу треба посветити обележеној линији. Линија 22 је пример замке у коју се често упада у алгоритмици и која се назива скривена сложеност. Ако посматрамо код као целину, код је прилично елегантно написан и из саме синтаксе се не може баш тако лако закључити да је ово решење неефикасно. Проблем у задатку је то што у свакој итерацији унутрашње и спољашње петље позива функција uzastopniRastuci() која проверава да ли сегмент испуњава тражени услов.

Сама функција uzastopniRastuci() инкрементално и истовремено одређује минимум и максимум сегмента. У најгорем случају дужина сегмента је $n$, па је временска сложеност функције $O(n)$, па ће укупна сложеност нашег решења бити $O(n^3)$. Проблем није у функцији uzastopniRastuci(), већ у начину на који је ми користимо. Користимо је у потпуности изоловано и за сваки сегмент изнова рачунамо потребне вредности. Управо то је скривена сложеност. Скривена сложеност је најчешће последица некритичке примене уграђених функција и неразумевања начина на који раде, као и недовоњно добро спроведене анализе проблема.

Нама није довољно да само инкрементално одредимо максимум и минимум једног конкретног сегмента, већ нам треба инкрементално решење које ће узети у обзир све сегменте који почињу на датој позицији $i$. Дакле, уместо да за сваки сегмент испочетка одређујемо његов максимум и минимум, ми треба инкрементално да одредимо максимум и минимум проширеног сегмента уз помоћ текућег (новог) елемента који додајемо у стари сегмент и знања о максимуму и минимуму полазног краћег сегмента.

Узимајући ово разматрање у обзир, комплетно инкрементално решење је дато у наставку:

static int zad5_inkrementalno(int[] niz)
{
    int maxDuzine = -1;
    for (int i = 0; i < niz.Length; i++)
    {
        int max = niz[i];
        int min = niz[i];
        for (int j = i; j < niz.Length; j++)
        {
            if (niz[j] < min)
                min = niz[j];
            if (niz[j] > max)
                max = niz[j];
            int duzina = j - i;
            int raspon = max - min;
            if (raspon == duzina && duzina > maxDuzine)
                maxDuzine = duzina;
        }
    }
    return maxDuzine + 1;
}

Инкрементално одрећивање сегмената који испуњавају тражени услов и ажурирање дужине најдужег је обележено у решењу приказаном изнад. Временска сложеност приказаног решења је $О(n^2)$, јер сваки сегмент низа разматрамо тачно једном у константном времену.

Задатак 6

Дат је низ a реалних бројева дужине $n$ и природан број $k$. Написати програм којим се у низу a одређује пози- ција почетка сегмента (подниза узастопних елемената) дужине $k$ са највећим просеком (ако више сегмената има исти просек, пријавити последњи од њих).

Улаз: У првој линији стандардног улаза налази се природан број $k$ ($k \le 5 \cdot 10^3$). У другој линији налази се природан број $n$ ($n \le 5 \cdot 10^5$). У следећих $n$ линија налазе се по један реалан број (ти бројеви представљају редом елементе низа $a$).

Излаз: На стандарном излазу приказати позицију почетка последњег сегмента дужине $k$ низа $a$ чији је просек највећи (позиције у низу се броје од нуле).

Решење

Као и до сада, наивно решење би значило да испитујемо све могуће сегменте дужине $k$. Дакле, у петљи ћемо фиксирати сваки могући почетак ($i$) сегмента и одредићемо просек сегмента дужине $k$ који почиње на тој позицији. Од свих тих сегмената, упамтићемо позицију на којој почиње онај са највећим просеком. Наивно решење је у наставку:

static double prosek(int[] niz, int i, int k)
{
    double z = 0;
    for (int j = 0; j < k; j++)
    {
        z += niz[j];
    }
    return z / k;
}
static int zad6_naivno(int[] niz, int k)
{
    int pocetakSegmenta = -1;
    double maxProsek = double.MinValue;
    for (int i = 0; i < niz.Length - k; i++)
    {
        double p = prosek(niz, i, k); 
        if (p > maxProsek)
        {
            maxProsek = p;
            pocetakSegmenta = i;
        }
    }
    return pocetakSegmenta;
}

Као и у претходном задатку, ово решење има проблема са скривеном сложеношћу која је обележена жутом бојом. Временска сложеност наивног решења је $O(n^2)$ и то се може значајно поправити.

Функција prosek() рачуна просек сегмента дужине $k$ који почиње на позицији $i$ на инкременталан начин, али не узима у обзир то да ми прелазимо са сегмента који почиње на позицији $i$ на сегмент који почиње на позицији $i+1$ и да та два сегмента деле велики број заједничких елемената. Чињеница да ови сегменти деле велики број заједничких елемената, треба да нам послужи као сигнал за могућу примену инкременталности. Дакле, уместо да испочетка рачунамо просек новог сегмента, треба да осмислимо како да искористимо просек старог сегмента при рачунању новог.

Идеју ћемо илустровати на конкретном примеру. Нека је дат низ следећи низ бројева

$$7 \quad 5 \quad 8 \quad 4 \quad 3 \quad 9 \quad 2 \quad 6 \quad 1 \quad 10$$

и нека је $k = 5$. Нека је $i=2$. Тада ће сегмент чији просек разматрамо бити

$$8 \quad 4 \quad 3 \quad 9 \quad 2.$$

Када пређемо на нову вредност параметра $i+1$, тј. $i=3$, тада ће сегмент који разматрамо бити:

$$4 \quad 3 \quad 9 \quad 2 \quad 6.$$

Просек рачунамо као збир елемената сегмента подељен са његовом дужином. С обзиром да су наши сегменти сви исте дужине, дељење можемо да елиминишемо из разматрања. Дакле, што је већи збир, биће већи и просек, па ћемо рачунати само збирове сегмената.

Ако елементе низа обележимо са $a_i$ и збир сегмента дужине $k$ који почисе на позицији $i$ са $Z_{i,k}, добићемо следеће:

$$\begin{aligned} Z_{2,5} &= 8+4+3+9+2 = 26 \\ Z_{3,5} &= 4+3+9+2+6 = 24 \end{aligned}$$

Посматрајући ова два израза, јасно је да приликом преласка са текућег на наредни сегмент, збир текућег сегмента треба да додам вредност новог елемента који у сегмент укључујемо и да њега одузмемо вредност елемента који из сегмента искључујемо. У нашем, примеру када пређем на $Z_{3,5}$, да бих одредио његову вредност потребно је да од $Z_{2,5}$ одузмем $а_2$ ($8$) и додам $а_7$ ($6$). У општем случају, инкрементална формула ће бити:

$$Z_{i+1, k} = Z_{i,k} - a_i + a_{i + k}.$$

Описана техника се назива покретни прозор и приказана је у следећем решењу:

static int zad6_inkrementalno(int[] niz, int k)
{
    int pocetakSegmenta = 0;
    double tekuciProsek = 0;
    for (int i = 0; i < k; i++)
        tekuciProsek += niz[i];
    double maxProsek = tekuciProsek;
    for (int i = 1; i < niz.Length - k; i++)
    {
        tekuciProsek = tekuciProsek - niz[i - 1] + niz[i + k - 1];
        if (tekuciProsek > maxProsek)
        {
            maxProsek = tekuciProsek;
            pocetakSegmenta = i;
        }
    }
    return pocetakSegmenta;
}

Приметимо да у инкременталном решењу које користи покретни прозор прво треба да одредимо збир првог сегмента (линије 4-6), а затим у петљи да инкрементално рачунамо прелазе на наредне сегменте (линија 10). Поред овога, треба приметити да позицију сегмента са максималним просеком такође рачунамо инкрементално. Временска сложеност приказаног инкременталног решења је линеарна, тј. $O(n)$.

Задатак 7

Панграми су речи које садрже бар једно појављивање сваког слова абецеде или азбуке (слова се могу појављи- вати и више пута). Чувени панграм у енглеском језику је “the quick brown fox jumps over a lazy dog”. Напиши програм који проверава да ли се у датом тексту налази неки подтекст (низ узастопних карактера) дужине $k$ који је панграм.

Улаз: Прва линија стандардног улаза садржи ниску састављену само од малих слова енглеске абецеде, дужине највише $10^5$ карактера. Наредни ред садржи природан број $k$ ($26 \le k \le 10^5$).

Излаз: На стандардни излаз исписати da ако у унетом тексту постоји панграм дужине $k$, односно ne у су- протном.

Решење

Као и у претходном задатку, потребно је да испитамо све сегменте дужине $k$ на свакој могућој почетној позицији $i$ у оригиналном тексту. Ради једноставности, раздвојићемо у посебне функције фиксирање почетне позиције и испитивање да ли је сегмент који почиње на тој позицији панграм.

Функција pangram() ће испитивати да ли је сегмент дужине $k$ који почиње на позицији $i$ панграм. Сегмент је панграм ако садржи сва могућа слова. Због тога можемо да користимо низ индикатора у којем ћемо чувати информацију о томе да ли се слово појавило или није. На крају, када прођемо кроз цео сегмент, потребно је само да проверимо да ли су сви индикатори у низу постављени на true. Ако наиђемо на неки индикатор који није постављен, јасно је да се неће радити о панграму.

Наивно решење је у наставку.

static bool pangram(string tekst, int i, int k)
{
    bool[] indikatori = new bool[26];
    for (int j = i; j < k; j++)
    {
        int kod = tekst[i + j] - 'a';
        indikatori[kod] = true;
    }
    for (int j = 0; j < k; j++)
    {
        if (indikatori[j] == false)
            return false;
    }
    return true;
}
static bool zad7_naivno(string tekst, int k)
{
    for (int i = 0; i < tekst.Length - k; i++)
    {
        if (pangram(tekst, i, k))
            return true;
    }
    return false;
}

Временска сложеност датог решење је $О(n^2)$, док је просторна сложеност константна. Иако користимо помоћни низ у решењу, треба приметити да је он константне величине и да не зависи од величине улаза, па ће према томе и просторна сложеност бити константна.

Као и претходни задатак и овај задатак има скривену сложеност у линији која је обележена жутом бојом. Проблем је у томе што ми не узимамо у обзир да наши сегменти деле велики број слова. Да бисмо учинили решење ефикасним, треба инкрементално да рачунамо прелаз са једног на други сегмент. Прецизније, потребно је да модификујемо наше решење на следећи начин:

• Можемо да користимо покретни прозор, јер приликом преласка на наредни сегмент треба да елиминишемо из низа индикатора почетно слово старог сегмента и да у низ индикатора додамо ново слово које додајемо на његов крај, чиме формирамо нови сегмент.
• У низу индикатора није довољно да чувамо информацију да ли се слово појавили или није, већ треба да проширимо информације тако да чувамо колико пута се слово појавило у сегменту. Разлог зашто је то потребно, крије се у чињеници да ћемо применом покретног прозора нека слова додавати у низ индикатора, а нека ћемо елиминисати. У случају да постоје дупликати, слово елиминишемо тек када последње појављивање елиминишемо из сегмента.
• Уместо да сваки пут изнова бројимо колико имамо различитих слова у низу индикатора, много је ефикасније да и ту информацију одржавамо инкрементално. Када први пут наиђемо на неко слово приликом додавања у низ индикатора тада ће њему придружена вредност прећи са $0$ на $1$ и тада треба да увећамо бројач различитих слова. Са друге стране, када елиминишемо последње појављивање слова из низа индикатора, тада ће њему придружена вредност прећи са $1$ на $0$ и тада треба да умањимо бројач различитих слова. Ако у било ком тренутку откријемо да је бројач различитих слова постао 26, то значи да смо утврдили да се ради о панграму.

Инкрементално решење које користи покретни прозор и инкрементално одржава вредност бројача различитих слова је у наставлу:

static bool zad7_inkrementalno(string tekst, int k)
{
    int[] brojacSlova = new int[26];
    int brojRazlicitih = 0;
    for (int i = 0; i < k; i++)
    {
        int kod = tekst[i] - 'a';
        if (brojacSlova[kod] == 0)
        {
            brojRazlicitih++;
        }
        brojacSlova[kod]++;
    }
    if (brojRazlicitih == 26)
    {
        return true;
    }
    for (int i = 1; i < tekst.Length - k; i++)
    {
        int kodIzbacivanje = tekst[i - 1] - 'a';
        int kodDodavanje = tekst[i + k - 1] - 'a';
        if (brojacSlova[kodIzbacivanje] == 1)
        {
            brojRazlicitih--;
        }
        brojacSlova[kodIzbacivanje]--;
        if (brojacSlova[kodDodavanje] == 0)
        {
            brojRazlicitih++;
        }
        brojacSlova[kodDodavanje]++;
        if (brojRazlicitih == 26)
        {
            return true;
        }
    }
    return false;
}

Временска сложеност приказаног решења је линеарна, тј. $O(n)$, а просторна сложеност је константна.