Z-algoritmi on O(n)-aikainen algoritmi, joka muodostaa merkkijonoa vastaavan Z-taulukon. Jokainen tässä taulukossa oleva luku kertoo, montako merkkiä siitä kohdasta alkava merkkijono täsmää merkkijonon alun kanssa.

Esimerkki Z-taulukosta

Tarkastellaan esimerkkinä merkkijonoa ABABCABABCB. Tämän merkkijonon Z-taulukko on seuraavanlainen:

A B A B C A B A B C B
- 0 2 0 0 5 0 2 0 0 0

Esimerkiksi taulukossa on toisen A:n kohdalla on luku 2, koska täsmäävä alkuosa on AB, jonka pituus on 2.

Algoritmin idea

Z-algoritmi vertaa joka kohdassa taulukon alkuosaa ja kyseisestä kohdasta alkavaa merkkijonoa merkki kerrallaan. Tavallisesti toteutettuna tämä veisi aikaa O(n^2), mutta algoritmissa on yksi tärkeä optimointi, jonka ansiosta aikaa kuluu vain O(n).

Ideana on pitää yllä tietoa siitä, mikä on tähän mennessä pisimmälle merkkijonossa yltänyt täsmäävä osa (oikea reuna), ja hyödyntää tätä tietoa seuraavien arvojen laskemisessa. Tarkastellaan esimerkkinä tilannetta, jossa olemme laskeneet seuraavat arvot taulukkoon:

A B A B C A B A B C B
- 0 2 0 0 5 0 ? ? ? ?

Tässä vaiheessa meillä on tietona, että 5:n pituinen täsmäävä osuus ulottuu merkkijonon toiseksi viimeiseen merkkiin asti. Niinpä voimme päätellä suoraan (vertaamatta merkkejä yksi kerrallaan), että seuraava luku on 2, koska vastaavassa kohdassa taulukon alussa on luku 2:

A B A B C A B A B C B
- 0 2 0 0 5 0 2 ? ? ?

Vastaavalla tavalla voimme päätellä myös kaksi seuraavaa lukua:

A B A B C A B A B C B
- 0 2 0 0 5 0 2 0 0 ?

Viimeisen luvun kohdalla meidän täytyy jälleen verrata merkkejä yksi kerrallaan, koska meillä ei ole aiempaa tietoa tästä merkkijonon osasta. Koska ensimmäiset merkit eivät täsmää, tuloksena on seuraava taulukko:

A B A B C A B A B C B
- 0 2 0 0 5 0 2 0 0 0

Aina kun vertaamme merkkejä yksi kerrallaan, muistissa oleva oikea reuna liikkuu, joten algoritmi vie aikaa vain O(n).

Algoritmin toteutus

Z-algoritmin toteutuksessa on monia yksityiskohtia, mutta se on mahdollista toteuttaa lyhyellä koodilla, jos tietää mitä tekee. Yksi lyhyt toteutus on tässä:

vector<int> create_z(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i=1; i<n; i++) {
        z[i] = max(0,min(z[i-l],r-i));
        while (i+z[i]<n && s[z[i]] == s[i+z[i]]) z[i]++;
        if (i+z[i] > r) {
            l=i; r=i+z[i];
        }
    }
    return z;
}

Tälle funktiolle annetaan parametrina tutkittava merkkijono ja se muodostaa O(n)-ajassa vektorin, jossa on Z-taulukon sisältö.

Algoritmin soveltaminen

Mitä Z-taulukolla sitten tekee? Osoittautuu, että voimme ratkaista sen avulla tehokkaasti monia merkkijonotehtäviä, kunhan muotoilemme tehtävän niin, että voimme hyödyntää Z-taulukossa olevaa tietoa. Pääset harjoittelemaan tätä tämän viikon tehtävissä.