Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Z-funktio kuvioiden hakuun

Vertaa prefiksejä merkkijonon eri kohdissa

Oppitunti 3/413 vaihetta

Z-funktio kuvioiden hakuun on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Toinen hakumenetelmä

Z-funktio on selkeä vaihtoehto KMP:lle hahmonten haussa. Monien mielestä sen toimintaa on helpompi hahmottaa. ✨

Mitä z[i] tarkoittaa

Jokaisella indeksillä z[i] on pisimmän indeksistä i alkavan osamerkkijonon pituus, kun osamerkkijono täsmää koko merkkijonon etuliitteeseen.

Pieni esimerkki

Merkkijonolle aabaab z-arvot ovat 0,1,0,3,1,0. Indeksissä 3 osuus aab täsmää etuliitteeseen, joten pituudeksi saadaan 3.

Z-ikkuna

Seuraamme ikkunaa [l, r], joka kuvaa tähän asti löydettyä oikeimmalle ulottuvaa osumaa. Näin voitte hyödyntää aiempia vertailuja uudelleen.

l, r = 0, 0

Ikkunan sisällä

Kun i on ikkunan sisällä, voitte kopioida tunnetun z-arvon alkuarvoksi, mutta arvoa rajoittaa ikkunan reuna.

if i < r:
    z[i] = min(r - i, z[i - l])

Ikkunan ulkopuolelle laajentaminen

Alkuarvon jälkeen jatkatte merkkien vertailua yksi kerrallaan niin kauan kuin ne täsmäävät etuliitteeseen.

while i + z[i] < n and s[z[i]] == s[i + z[i]]:
    z[i] += 1

Ikkunan siirtäminen eteenpäin

Jos osuma ulottuu kauemmas oikealle, päivittäkää l ja r, jotta tulevat indeksit voivat hyödyntää sitä.

if i + z[i] > r:
    l, r = i, i + z[i]

Lineaarisen ajan takuu

Ikkuna liikkuu vain oikealle, joten kokonaisaikavaativuus on O(n). Jokainen merkki aiheuttaa vain rajallisen määrän työtä.

Haku Z-funktiolla

Yhdistäkää pattern + sep + text ja laskekaa Z-arvot. Jokainen hahmonten pituutta vastaava z-arvo tarkoittaa osumaa.

combined = pattern + chr(0) + text
z = z_function(combined)

Osumien lukeminen

Käykää Z-taulukko läpi; aina kun z[i] == len(pattern), osuma alkaa vastaavasta kohdasta tekstissä.

if z[i] == len(pattern):
    matches.append(i - len(pattern) - 1)

Z-funktio ja KMP

Sekä Z-funktio että KMP toimivat lineaarisessa ajassa. Z-funktio on usein helpompi koodata, joten se on erinomainen varamenetelmä työkalupakissanne.

Pikatarkistus

Varmistakaa, että Z-taulukon merkitys on teille selvä.

Vastaa interaktiivisessa oppitunnissa

Kertaus: Z-funktio toimii

Rakensitte Z-taulukon liukuvan ikkunan avulla, suorititte haun lineaarisessa ajassa ja saitte käyttöönne selkeän vaihtoehdon KMP:lle. 🎯

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Z-funktio kuvioiden hakuun” ilmainen?

Kyllä – oppitunnin ”Z-funktio kuvioiden hakuun” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Z-funktio kuvioiden hakuun”?

Vertaa prefiksejä merkkijonon eri kohdissa Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.

Kuinka kauan ”Z-funktio kuvioiden hakuun”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin