Præfiks funktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. april 2022; checks kræver 4 redigeringer .

Præfiksfunktionen for en streng og en position i den er længden af ​​det største egentlige (ikke lig med hele understrengen) præfiks for understrengen , som også er suffikset for denne understreng.

Det vil sige, at i begyndelsen af ​​en understreng med længde skal du finde et sådant præfiks af den maksimale længde , der ville være suffikset af denne understreng .

Benævnt ; hvor  er en streng;  er længden af ​​delstrengen i S. Det antages, at .

Ofte er præfiksfunktionen defineret i vektorform:

Præfiksfunktionen for en streng er en vektor , hvis element er lig med .

For en streng vil præfiksfunktionen f.eks. være: .

Denne funktion bruges for eksempel i Knuth-Morris-Pratt-algoritmen .

Beregningsalgoritme

Søge efter gentagne stavelser ikke i et ord, men i en tekst, en linje, der starter fra de første tegn? Linjetegn er nummereret fra 1.

Lad . Lad os prøve at beregne præfiksfunktionen for .

Hvis , så selvfølgelig . Hvis ikke, prøv mindre suffikser. Det er ikke nødvendigt at gentage alle suffikser med en lineær søgning. Du kan bruge de allerede beregnede værdier af præfiksfunktionen. Du kan se, at det også vil være suffikset på strengen , da  det er længden af ​​det maksimale præfiks-suffiks på dette tidspunkt. For enhver streng vil der ikke være noget suffiks. Algoritmen viser sig således:

  1. Når  - put .
  2. Ellers når  - sætte .
  3. Ellers skal du installere og gå til trin 1.

For en streng 'abcdabcabcdabcdab'ville beregningen være:

1S[1]='a', k=π=0; 2S[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;

Og resultatet er [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6]:.

Arbejdshastighed

På trods af at punkt 3 er en indre sløjfe, estimeres beregningstiden for præfiksfunktionen til . Lad os bevise det.

Alle er opdelt i:

  1. øges med én. Sløjfen gennemgår én iteration.
  2. Ændrer ikke nul . Sløjfen gennemgår også én iteration. Case 1 og 2 i alt ikke mere end styk.
  3. Du må ikke ændre eller reducere det positive . Da værdien kun kan falde inde i løkken, og stigningen kun er mulig med én, kan den samlede værdi ikke falde mere end én gang, hvilket begrænser antallet af gange, den indre løkke udføres.

I alt kræver algoritmen ikke mere end iterationer, hvilket beviser rækkefølgen af ​​hastighed . Det "værste" for algoritmen er tilfældet med at behandle en streng af formularen . 'aa…ab'

Implementeringseksempel i Python

def præfiks ( s ):     p = [ 0 ] * len ( s )     for i i området ( 1 , len ( s ) ):         k = p [ i - 1 ]         mens k > 0 og s [ k ] != s [ i ]:             k = p [ k - 1 ]         hvis s [ k ] == s [ i ]:             k += 1         p [ i ] = k     returner p

Links

 Strenge
String lighedsmål
Understrengssøgning
palindromer
Sekvensjustering
Suffiksstrukturer
Andet