Előtag funkció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 12-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A karakterlánc és a benne lévő pozíció előtagfüggvénye a karakterlánc legnagyobb saját (nem egyenlő a teljes részkarakterlánccal) előtagjának hossza , amely egyben ennek a részstringnek az utótagja is .

Azaz egy hosszúságú részkarakterlánc elején meg kell találnia egy olyan maximális hosszúságú előtagot, amely ennek a részkarakterláncnak az utótagja lenne .

Jelölve ; hol  van egy karakterlánc;  az S-beli részkarakterlánc hossza. Feltételezzük, hogy .

Az előtag függvényt gyakran vektoros formában határozzák meg:

Egy karakterlánc előtagfüggvénye egy vektor , amelynek minden eleme egyenlő a -val .

Például egy karakterlánc esetén az előtag függvény a következő lenne: .

Ezt a függvényt például a Knuth-Morris-Pratt algoritmus használja .

Számítási algoritmus

Ismétlődő szótagokat keresni nem szóban, hanem szövegben, az első karakterektől kezdődő sorban? A sor karakterei 1-től vannak számozva.

Hadd . Próbáljuk meg kiszámítani az előtagfüggvényt .

Ha , akkor természetesen . Ha nem, próbálkozzon kisebb utótagokkal. Nem szükséges az összes utótagot végigvinni lineáris kereséssel. Használhatja az előtag függvény már kiszámított értékeit. Látható, hogy ez lesz a karakterlánc utótagja is , mivel  ezen a ponton a maximális előtag-utótag hossza. Egyetlen karakterlánchoz sem lesz utótag. Így az algoritmus a következőképpen alakul:

  1. Mikor  - tegye .
  2. Ellenkező esetben amikor  - fel .
  3. Ellenkező esetben telepítse, és folytassa az 1. lépéssel.

Egy karakterlánc esetén a 'abcdabcabcdabcdab'számítás a következő lenne:

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;

Az eredmény pedig: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].

Munka sebessége

Annak ellenére, hogy a 3. tétel egy belső hurok, az előtag függvény számítási idejét a következőre becsüljük . Bizonyítsuk be.

Mindegyik a következőkre oszlik:

  1. eggyel növelve . A ciklus egy iteráción megy keresztül.
  2. Nem változik a nulla . A ciklus is egy iteráción megy keresztül. Az 1. és 2. eset összesen nem több, mint darab.
  3. Ne változtassa meg vagy csökkentse a pozitívumot . Mivel az érték csak a cikluson belül csökkenhet, a növekedés pedig csak eggyel lehetséges, ezért a teljes érték nem csökkenhet többször, ami korlátozza a belső ciklus végrehajtásának számát.

Összességében az algoritmus nem igényel több iterációt, ami bizonyítja a sebesség sorrendjét . Az algoritmus számára a „legrosszabb” egy formátumú karakterlánc feldolgozásának esete . 'aa…ab'

Megvalósítási példa Pythonban

def előtag ( s ):     p = [ 0 ] * len ( s )     i tartományban ( 1 , len ( ek ) ): k = p [ i - 1 ] míg k > 0 és s [ k ] ! = s [ i ]: k = p [ k - 1 ] ha s [ k ] == s [ i ]: k += 1 p [ i ] = k visszatér p                                                            

Linkek

 Húrok
Karakterlánc hasonlósági mértékek
Substring keresés
palindromák
Sorozat-igazítás
Utótag szerkezetek
Egyéb