Etuliitetoiminto

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Merkkijonon etuliitefunktio ja paikka siinä on alimerkkijonon suurimman varsinaisen (ei yhtä suuri kuin koko osamerkkijonon) etuliitteen pituus , joka on myös tämän osamerkkijonon pääte . $S$ $i$ $k$ $S[1..i]$

Toisin sanoen pituuden alimerkkijonon alusta on löydettävä sellainen maksimipituinen etuliite, joka olisi tämän osamerkkijonon pääte . $S[1..i]$ $i$ $k<i$ $\left(S[1..k]=S\left[(i-k+1)..i\right]\right)$

Merkitty ; missä on merkkijono; on S:n osamerkkijonon pituus. Oletetaan, että . ${\näyttötyyli \pi (S,i)}$ ${\displaystyle S\in \Sigma ^{+))$ $1\leqslant i\leqslant \left|S\right|$ $\pi (S,1)=0$

Usein etuliitefunktio määritellään vektorimuodossa:

Merkkijonon etuliitefunktio on vektori , jonka jokainen elementti on yhtä suuri kuin . ${\displaystyle S\in \Sigma ^{+))$ ${\displaystyle \pi (S)\in \mathbb {Z} ^{\left|S\right|))$ $i$ ${\näyttötyyli \pi (S,i)}$

Esimerkiksi merkkijonolle etuliitefunktio olisi: . ${\texttt {abcdabscabcdabia))$ $\pi ({\texttt {abcdabscabcdabia)))=[0,0,0,0,1,2,0,0,1,2,3,4,5,6,0,1]$

Tätä funktiota käytetään esimerkiksi Knuth-Morris-Pratt-algoritmissa .

Laskenta-algoritmi

Etsi toistuvia tavuja ei sanasta, vaan tekstistä, riviltä, joka alkaa ensimmäisistä merkeistä? Rivimerkit numeroidaan 1:stä alkaen.

Anna . Yritetään laskea etuliitefunktio . $\pi (S,i)=k$ $i+1$

Jos , niin tietysti . Jos ei, kokeile pienempiä jälkiliitteitä. Lineaarisella haulla ei tarvitse iteroida kaikkia jälkiliitteitä. Voit käyttää etuliitefunktion jo laskettuja arvoja. Voit nähdä, että se on myös merkkijonon pääte , koska se on maksimietuliite-liitteen pituus tässä vaiheessa. Millä tahansa merkkijonolla ei ole jälkiliitettä. Siten algoritmista tulee: $S[i+1]=S[k+1]$ $\pi (S,i+1)=k+1$ $S[1\ldots \pi (S,k)]$ $S[1\ldots i]$ $k$ $j\in(k,i)$ $S[1\ldots j]$

Milloin - laittaa . $S[i+1]=S[k+1]$ $\pi (S,i+1)=k+1$
Muuten, kun - laittaa . $k = 0$ $\pi (S,i+1)=0$
Muussa tapauksessa asenna ja siirry vaiheeseen 1. $k:=\pi (S,k)$

Merkkijonolle 'abcdabcabcdabcdab'laskenta olisi seuraava:

1 S[1] = 'a', k = π = 0; 2 S[2]='b'!=S[k+1] => k=π=0; 3 S[3]='c'!=S[1] => k=π=0; 4 S[4]='d'!=S[1] => k=π=0; 5 S[5]='a'==S[1] => k=π=1; 6 S[6]='b'==S[2] => k=π=2; 7 S[7]='c'==S[3] => k=π=3; 8 S[8]='a'!=S[4] => k:=π(S, 3)=0, S[8]==S[1] => k=π=1; 9 S[9]='b'==S[2] => k=π=2; 10 S[10]='c'==S[3] => k=π=3; 11 S[11]='d'==S[4] => k=π=4; 12 S[12]='a'==S[5] => k=π=5; 13 S[13]='b'==S[6] => k=π=6; 14 S[14]='c'==S[7] => k=π=7; 15 S[15]='d'!=S[8] => k:=π(S,7)=3, S[15]==S[4] => k=π=4; 16 S[16]='a'==S[5] => k=π=5; 17 S[17]='b'==S[6] => k=π=6;

Ja tulos on: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].

Työn nopeus

Huolimatta siitä, että kohta 3 on sisäsilmukka, etuliitefunktion laskenta-aika on arvioitu . Todistetaan se. $O(|S|)$

Kaikki on jaettu: $i$

kasvaa yhdellä. Silmukka käy läpi yhden iteraation. $k$
Ei vaihda nollaa . Silmukka käy myös yhden iteraation läpi. Tapaukset 1 ja 2 yhteensä enintään kappaletta. $k$ $\left|S\right|-1$
Älä muuta tai vähennä positiivista . Koska arvo voi pienentyä vain silmukan sisällä, ja lisäys on mahdollista vain yhdellä, kokonaisarvo ei voi laskea useammin kuin kerran, mikä rajoittaa sisemmän silmukan suorituskertoja. $k$ $k$ $k$ $k$ $\left|S\right|-2$

Kaiken kaikkiaan algoritmi ei vaadi enempää kuin iteraatioita, mikä todistaa nopeuden järjestyksen . Algoritmin "pahin" on muodon merkkijonon käsittely . $2\left|S\right|$ $O(\left|S\right|)$ 'aa…ab'

Toteutusesimerkki Pythonissa

def - etuliite ( s ): p = [ 0 ] * len ( s ) i :lle alueella ( 1 , len ( s ) ): k = p [ i - 1 ] kun taas k > 0 ja s [ k ] != s [ i ]: k = p [ k - 1 ] jos s [ k ] == s [ i ]: k += 1 p [ i ] = k paluu p

Linkit

Alimerkkijonohaku ja siihen liittyvät kysymykset arkistoitu 15. tammikuuta 2016 Wayback Machinessa - Habr -artikkeli

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
muu	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono