Programozás | Java, JSP » Fenyvesi Tibor - A Dömölki féle Shift-And sztringkereső algoritmus

A Dömölki-féle Shift-And sztringkereső algoritmus - alapsztring: ABAFBADC (ebben keresünk) - mintaszring: BAD (ezt keressük, hossza: m) - U vektor: {100} (bináris 1-gyel kezdődik, hossza m) - V vektor: {001} (bináris 1-re végződik, hossza m) - Az U és a V vektor fix, értékük nem változik - D vektor: {000} (csupa bináris nullával indít, hossza m, és változik) B logikai (bit)mátrix: (oszlopai a minta karakterei, sorai az alapsztringben előforduló betűk felsorolva Kitöltése: soronként haladva, ahol az alapsztring betűje (1. oszlop) szerepel a mintasztringben, ott egy 1-est kell írni, egyébként 0-át: A B F D C B 0 1 0 0 0 A 1 0 0 0 0 D 0 0 0 1 0 A ∨ művelet bitenként hasonlítja össze a vektorokat, és ha valamelyik 1, akkor 1, egyébként 0 a végeredmény. A ∧ művelet bitenként hasonlítja össze a vektorokat, és ha mindkettő 1, akkor 1, egyébként 0 a végeredmény. pl. 0101 ∨ 1100 1101 1010 ∧ 0011 0010 Mehet a vizsgálat

i=1-től: Képlet: D’=(Shift(D)∨U)∧Bai (Bai a bitmátrix megfelelő sorvektora, pl. az A betűnél {0,1,0}) (A Shift jobbra tolja a bitvektort, az utolsó bit elvész, előre 0 ugrik be.) Vizsgálat: D’∧V egyenlő-e V-vel, azaz D’ utolsó bitje 1-e? Ha igen, találat, sőt, az i-m+1 képlet megadja a minta kezdőpozícióját az alapsztringben! A vizsgálat mehet tovább, ha van még az alapsztringből, mivel még lehet találat. Tehát a példa (az alapsztring betűit vesszük sorra!) i=1, ’A’ betű: D Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {0,0,0} {0,0,0} {1,0,0} {1,0,0} {0,1,0} (1. sor a mátrixból) {0,0,0} (0 a vége, találat: Ø) i=2, ’B’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {0,0,0} {0,0,0} {1,0,0} {1,0,0} {1,0,0} (2. sor a mátrixból) {1,0,0} (0 a vége, találat: Ø) i=3, ’A’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {1,0,0} {0,1,0} {1,0,0} {1,1,0} {0,1,0} (1. sor a

mátrixból) {0,1,0} (0 a vége, találat: Ø) i=4, ’F’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {0,1,0} {0,0,1} {1,0,0} {1,0,1} {0,0,0} (3. sor a mátrixból) {0,0,0} (0 a vége, találat: Ø) i=5, ’B’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {0,0,0} {0,0,0} {1,0,0} {1,0,0} {1,0,0} (2. sor a mátrixból) {1,0,0} (0 a vége, találat: Ø) i=6, ’A’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {1,0,0} {0,1,0} {1,0,0} {1,1,0} {0,1,0} (1. sor a mátrixból) {0,1,0} (0 a vége, találat: Ø) i=7, ’D’ betű: D=D’ Shift(D) U Shift(D)∨U Bai D’=(Shift(D)∨U)∧Bai {0,1,0} {0,0,1} {1,0,0} {1,0,1} {0,0,1} (4. sor a mátrixból) {0,0,1} (1 a vége, TALÁLAT!) Tehát a 7-3+1= 5. pozíciótól kezdve van az (első) találat! JAVA példaprogram magyarázatokkal: *-----------------------------------------------------------------------------import java.utilScanner; public class Dömölki {

public static void main(String[] args) { /* input billentyűzetről Scanner sc=new Scanner(System.in); System.outprintln("Alapsztring: "); String alap = sc.next(); System.outprintln("Mintasztring: "); String minta = sc.next(); */ // vagy fix bemenet String alap = "ABABBERTUABAB"; String minta = "BAB"; int int int int int int int ah = alap.length(); //alapsztring hossza mh = minta.length(); // mintasztring hossza u = (int)Math.pow(2,mh-1); // U vektor decimális formátumban v = 1; // V vektor decimális formátumban d = 0; // D vektor decimális formátumban b; // B vektor (a bitmátrix aktuális sorvektora decimális formátumban) t = 0; //találatszámláló // hajrá! int i,j; // az alap- ill. a mintasztring egy karakterének sorszáma char abetu, mbetu; // az alap- ill. a mintasztring egy karaktere for(i=0;i<ah;i++) { abetu = alap.charAt(i); // B vektor meghatározása b = 0; for(j=0;j<mh;j++) { mbetu = minta.charAt(j); if (abetu ==

mbetu) b = b + (int)Math.pow(2,(mh-1)-j); } // mehet a vizsgálat //d = d >>> 1; // Shift(D) jobbra 1 bittel, balra előre 0 beszúr //d = d |u; // Shift(D)|U //d = d & b; // (Shift(D)|U)& B d = ((d >>> 1)|u) & b; // előbbi 3 sor egyben if ((d & v)==v) { // D utolsó bitje 1? System.outprintln(i+1-mh+1); t++; } } System.outprintln("------------------"); System.outprintln((t==0) ? "Nincs találat!" : "Találatok száma: "+t); } } *-----------------------------------------------------------------------------Készítette: Fenyvesi Tibor (tibsi@freemail.hu)