• Hlavní stránka
  • Balíky
  • Třídy
  • Soubory
  • Seznam souborů

Algoritmus.java

Zobrazit dokumentaci tohoto souboru.
00001 /******************************************************************************
00002  * Název projektu: Aplet pro demonstraci Boyerova-Mooreova algoritmu
00003  * Balíček: boyermooredemo
00004  * Soubor: Algoritmus.java
00005  * Datum:  15.4.2008
00006  * Poslední změna: 18.4.2008
00007  * Autor:  Jaroslav Dytrych xdytry00
00008  *
00009  * Popis: Třída, kteá provádí vyhledávání řetězce v textu pomocí
00010  *        Boyerova-Mooreova algoritmu a ukládá informace do seznamu změn
00011  *        uživatelského rozhraní, které budou následně využity při vizualizaci.
00012  *             Jako počítadlo kroků využívá proměnnou pro počet kroků z appletu,
00013  *        čímž zajistí správnou hodnotu této proměnné po dokončení operace při
00014  *        ukončení v libovolném bodě.
00015  *             Aby se nevytvářely zbytečné instance konstant, využívá instanci 
00016  *        třídy konstant, kterou vlastní applet.
00017  *        
00018  ******************************************************************************/
00019 
00020 /**
00021  * @file Algoritmus.java
00022  * 
00023  * @brief Třída Algoritmus - vyhledávání v řetězci a tvorba seznamu změn GUI
00024  */
00025 
00026 package boyermooredemo;
00027 
00028 import java.util.Iterator;
00029 import java.util.TreeMap;
00030 
00031 /**
00032  * Třída, kteá provádí vyhledávání řetězce v textu pomocí Boyerova-Mooreova 
00033  * algoritmu a ukládá informace do seznamu změn uživatelského rozhraní, 
00034  * které budou následně využity při vizualizaci.
00035  *      Jako počítadlo kroků využívá proměnnou pro počet kroků z appletu, čímž 
00036  * zajistí správnou hodnotu této proměnné po dokončení operace při ukončení 
00037  * v libovolném bodě.
00038  *      Aby se nevytvářely zbytečné instance konstant, využívá instanci třídy 
00039  * konstant, kterou vlastní applet.
00040  * 
00041  * @brief Vyhledávání v řetězci a tvorba seznamu změn GUI
00042  */
00043 public class Algoritmus {
00044   /**
00045    * Reference na applet pro demonstraci algoritmu
00046    */
00047   private AppletBoyerMooreDemo ABMD;
00048 
00049   /** prohledávaný text */
00050   private char[] text;
00051   /** hledaný řetězec */
00052   private char[] pat;
00053   /** délka hledaného řetězce */
00054   private int m;
00055   /** délka prohledávaného textu */
00056   private int n;
00057   /** kontejner delta1 */
00058   private TreeMap<Character,Integer> delta1;
00059   /** delta1 pro znaky, které nejsou v kontejneru */
00060   private int delta1Jine;
00061   /** pole delta2 */
00062   private int[] delta2;
00063   /** pole shoda */
00064   private int[] shoda;
00065   
00066   /** pomocný kontejner pro vizualizaci - uchovává souřadnice v tabulce */
00067   private TreeMap<Character,Integer> poziceVDelta1;
00068   /** pomocná proměnná pro vizualizaci - počet položek v tabulce delta1 */
00069   private int pocetVDelta1;
00070 
00071 
00072   /**
00073    * Konstruktor třídy
00074    *
00075    * @param apABMD Reference na applet pro demonstraci algoritmu
00076    */
00077   public Algoritmus(AppletBoyerMooreDemo apABMD) 
00078   {
00079     ABMD = apABMD;  // uloží referenci na applet
00080   }
00081   
00082   /**
00083    * Metoda pro vyhledávání řetězce v textu a tvorbu seznamu změn uživatelského 
00084    * rozhraní pro vizualizaci. Nastavuje také počet kroků vizualizace ve třídě 
00085    * appletu.
00086    *
00087    * @param P Vyhledávaný řetězec
00088    * @param T Prohledávaný text
00089    * @return Vrací pozici vyhledávaného řetězce v prohledávaném textu, nebo -1, 
00090    *         pokud se řetězec v textu nevyskytuje.
00091    */
00092   public int BMA(String P, String T)
00093   {
00094     Integer pomI;  // pomocná proměnná pro zobrazení
00095     Character pomC;  // pomocná proměnná pro zobrazení
00096     int vypsano = 0;  // pomocná proměnná pro zobrazení - počet vypsaných znaků textu
00097     int posun = 0;  // pomocná proměnná pro zobrazení - posunutí v tabulce R
00098     int pomPosun = 0;  // pomocná proměnná pro zobrazení
00099     int pom;  // pomocná proměnná pro zobrazení
00100     int zvyrazneno = 0;  // pomocná proměnná pro zobrazení - počet zvýrazněných 
00101                          // sloupců v tabulce SR
00102     int presah;  // velikost tabulky SR je 3 * m + presah, přičemž 3*m je nezbytný 
00103                  // manipulační prostor a presah je pro větší přehlednost
00104     int pomITD1 = 1;  // pomocný index do tabulky delta1 pro vizualizaci
00105   
00106 
00107     m = P.length();  // délka hledaného řetězce
00108     
00109     // výpočet přesahu nutné velikosti tabulky SR
00110     if ((3*m+5) > ABMD.kon.TAB_SR_VR[1])
00111     {  // pokud je výchozí velikost tabulky malá (přesah 5 znaků by se nevešel)
00112       presah = 5;  // přesah bude 5 znaků
00113     }
00114     else
00115     {  // pokud je výchozí velikost tabulky dostatečná, jako přesah se využije
00116        // celá zbývající část tabulky
00117       presah = ABMD.kon.TAB_SR_VR[1] - 3*m;
00118     }
00119     
00120     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00121     // uloží informace o změně zobrazení - proměnná m, posun v algoritmu
00122     pomI = new Integer(m);
00123     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00124                                           ABMD.kon.PROM_M,pomI.toString()));
00125     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,11));
00126 
00127 
00128     pat = new char[m + 1];
00129     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00130     // uloží informace o změně zobrazení - posun v alg., rozměry tabulky, i=0 do tabulky
00131     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,13));
00132     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_R,
00133                                           ABMD.kon.TAB_D2,4,m+2));
00134     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00135                                           ABMD.kon.TAB_D2,0,1,"0"));
00136     for (int i = 0; i < m; i++)
00137     {  // uloží hledaný řetězec do pole pat
00138       pat[i+1] = P.charAt(i);
00139       // uloží informace o změně zobrazení - i do tabulky
00140       pomI = new Integer(i+1);
00141       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00142                                             ABMD.kon.TAB_D2,0,i+2,pomI.toString()));
00143       // uloží informace o změně zobrazení - pat[i] do tabulky
00144       pomC = new Character(pat[i+1]);
00145       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00146                                             ABMD.kon.TAB_D2,1,i+2,pomC.toString()));
00147     }
00148     
00149     n = T.length();  // délka prohledávaného textu
00150     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00151     // uloží informace o změně zobrazení - proměnná n, posun v algoritmu
00152     pomI = new Integer(n);
00153     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00154                                           ABMD.kon.PROM_N,pomI.toString()));
00155     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,15));
00156     
00157     text = new char[n + 1];
00158     for (int i = 0; i < n; i++)
00159     {  // uloží prohledávaný řetězec do pole text
00160       text[i+1] = T.charAt(i);
00161     }
00162     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00163     // uloží informace o změně zobrazení - posun v algoritmu
00164     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,17));
00165     
00166     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00167     // uloží informace o změně zobrazení - záměna bloku, posun na správný řádek
00168     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,
00169                                           ABMD.kon.ZADNY_RADEK));
00170     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_B,
00171                                           ABMD.kon.BLOK_DELTA1));
00172     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,42));
00173         
00174     vypocetDelta1();  // výpočet tabulky delta1
00175         
00176     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00177     // uloží informace o změně zobrazení - záměna bloku, posun na správný řádek
00178     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,
00179                                           ABMD.kon.ZADNY_RADEK));
00180     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_B,
00181                                           ABMD.kon.BLOK_BMA));
00182     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,20));
00183 
00184     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00185     // uloží informace o změně zobrazení - záměna bloku, posun na správný řádek
00186     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,
00187                                           ABMD.kon.ZADNY_RADEK));
00188     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_B,
00189                                           ABMD.kon.BLOK_DELTA2));
00190     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,54));
00191 
00192     vypocetDelta2();  // výpočet tabulky delta2
00193     
00194     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00195     // uloží informace o změně zobrazení - záměna bloku, posun na správný řádek, 
00196     // změna rozměrů tabulky SR
00197     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,
00198                                           ABMD.kon.ZADNY_RADEK));
00199     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_B,
00200                                           ABMD.kon.BLOK_BMA));
00201     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,21));
00202     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_R,
00203                                           ABMD.kon.TAB_SR,2,3*m+presah));
00204     
00205     int i = 1;  // pozice v textu
00206     
00207     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00208     // vizualizace - posun v algoritmu, změna popisků, nastavení proměnných, 
00209     // vložení řetězců do tabulky SR
00210     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,23));
00211     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_PO,
00212                                           ABMD.kon.POPISEK_IJ,ABMD.kon.TEXTY_POPISKU_IPJ));
00213     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_PO,
00214                                           ABMD.kon.POPISEK_MJ,ABMD.kon.TEXTY_POPISKU_NM)); 
00215     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_PO,
00216                                           ABMD.kon.POPISEK_L,ABMD.kon.TEXTY_POPISKU_D1P)); 
00217     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,ABMD.kon.PROM_I,"1"));
00218     pomI = new Integer(n-m+1);
00219     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00220                                           ABMD.kon.PROM_MJ,"1"));
00221     for (int z = 0; z < m; z++)
00222     {  // vložení pat do tabulky SR
00223       pomC = new Character(pat[z+1]);
00224       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00225                                             ABMD.kon.TAB_SR,0,z+m,pomC.toString()));
00226     }
00227     for (int z = 0; (z < (2*m+presah)) && (vypsano < n); z++)
00228     {  // vložení textu do tabulky SR
00229       pomC = new Character(text[z+1]);
00230       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00231                                             ABMD.kon.TAB_SR,1,z+m,pomC.toString()));
00232       vypsano++;  // aktualizace počtu vypsaných znaků
00233     }
00234     
00235     int j = 1;  // pozice v pat, kvůli vizualizaci inicializována na 1, která se zahodí
00236     Integer d1P;  // pomocná delta1
00237     
00238     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00239     // vizualizace - posun v algoritmu
00240     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,26));
00241     
00242     
00243     while (i <= (n-m+1))
00244     {  
00245       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00246       // vizualizace - odbarvení buněk
00247       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00248                                             ABMD.kon.TAB_D2,0,j+1,
00249                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00250       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00251                                             ABMD.kon.TAB_D2,3,j+1,
00252                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00253       for (int z = 3*m+presah-1; z >= 0; z--)
00254       {  // zkrácení zvýraznění na 1
00255         if ((z >= (2*m - 1)) && (z < (2*m)))
00256         {  // pokud má být buňka zvýrazněná
00257           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00258                                                 ABMD.kon.TAB_SR,0,z,
00259                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00260           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00261                                                 ABMD.kon.TAB_SR,1,z,
00262                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00263         }
00264         else
00265         {  // pokud buňka nemá být zvýrazněná
00266           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00267                                                 ABMD.kon.TAB_SR,0,z,
00268                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00269           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,
00270                                                 ABMD.kon.ZM_T_B,ABMD.kon.TAB_SR,1,z,
00271                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00272         }
00273       }  // zkrácení zvýraznění na 1
00274        
00275       j = m;
00276       
00277       // vizualizace - posun v algoritmu, nastavení proměnné
00278       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,27));
00279       pomI = new Integer(j);
00280       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00281                                             ABMD.kon.PROM_J,pomI.toString()));
00282       pomI = new Integer(i+j-1);
00283       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00284                                             ABMD.kon.PROM_IJ,pomI.toString()));
00285       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00286                                             ABMD.kon.TAB_D2,0,j+1,
00287                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00288       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00289                                             ABMD.kon.TAB_D2,3,j+1,
00290                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00291       
00292       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00293       // vizualizace - posun v algoritmu, zvýraznění v tabulce
00294       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,28));
00295       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00296                                             ABMD.kon.TAB_SR,0,j+m-1,
00297                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00298       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00299                                             ABMD.kon.TAB_SR,1,j+m-1,
00300                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00301       zvyrazneno = 1;  // aktualizuje počet zvýrazněných sloupců
00302       
00303       while ((j >= 1) && (pat[j] == text[i+j-1]))
00304       {  // dokud do chází ke shodě, testuje další znaky
00305         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00306         // vizualizace - odbarvení buněk
00307         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00308                                               ABMD.kon.TAB_D2,0,j+1,
00309                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00310         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00311                                               ABMD.kon.TAB_D2,3,j+1,
00312                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00313       
00314         j--;
00315         
00316         // vizualizace - posun v algoritmu, nastavení proměnných, úprava tabulek
00317         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00318                                               ABMD.kon.TAB_D2,0,j+1,
00319                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00320         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00321                                               ABMD.kon.TAB_D2,3,j+1,
00322                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00323         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,29));
00324         pomI = new Integer(j);
00325         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00326                                               ABMD.kon.PROM_J,pomI.toString()));
00327         pomI = new Integer(i+j-1);
00328         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00329                                               ABMD.kon.PROM_IJ,pomI.toString()));
00330         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00331                                               ABMD.kon.TAB_SR,0,j+m-1,
00332                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00333         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00334                                               ABMD.kon.TAB_SR,1,j+m-1,
00335                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00336         zvyrazneno++;
00337       }  // dokud do chází ke shodě, testuje další znaky
00338       
00339       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00340       // vizualizace - posun v algoritmu, úprava tabulek
00341       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,30));
00342       
00343       if (j == 0)
00344       {  // pokud byl řetězec nalezen
00345         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00346         // vizualizace - posun v algoritmu, zrušení zvýraznění, nastavení proměnných
00347         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,31));
00348         for (int z = 0; z < 3*m; z++)
00349         {  // zrušení zvýraznění v tabulce SR
00350           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00351                                                 ABMD.kon.TAB_SR,0,z,
00352                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00353           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00354                                                 ABMD.kon.TAB_SR,1,z,
00355                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00356         }
00357         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00358                                               ABMD.kon.TAB_D2,0,j+1,
00359                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00360         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00361                                               ABMD.kon.TAB_D2,3,j+1,
00362                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00363         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00364                                               ABMD.kon.PROM_I,""));
00365         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00366                                               ABMD.kon.PROM_J,""));
00367         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00368                                               ABMD.kon.PROM_IJ,""));
00369         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00370                                               ABMD.kon.PROM_MJ,""));
00371         pomI = new Integer(i-1);
00372         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00373                                               ABMD.kon.PROM_POZ,pomI.toString()));
00374       
00375         return i-1;  // řetězec v poli začíná o 1 dál
00376       }
00377       else
00378       {  // pokud řetězec nebyl nalezen
00379         d1P = delta1.get(text[i+j-1]);
00380         
00381         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00382         // vizualizace - posun v algoritmu, úprava zvýraznění, nastavení proměnných
00383         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,33));
00384         if (d1P != null)
00385         {  // pokud d1P není null
00386           pomI = new Integer(d1P);
00387           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00388                                                 ABMD.kon.PROM_L,pomI.toString()));
00389           pomC = new Character(text[i+j-1]);
00390           pomITD1 = poziceVDelta1.get(pomC);
00391           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00392                                                 ABMD.kon.TAB_D1,0,pomITD1,
00393                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00394           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00395                                                 ABMD.kon.TAB_D1,1,pomITD1,
00396                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00397         }
00398         else
00399         {  // pokud je d1P null
00400           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00401                                                 ABMD.kon.PROM_L,"null"));
00402           pomITD1 = pocetVDelta1 - 1;
00403           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00404                                                 ABMD.kon.TAB_D1,0,pomITD1,
00405                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00406           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00407                                                 ABMD.kon.TAB_D1,1,pomITD1,
00408                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00409         }
00410         
00411         if (d1P == null)
00412         {  // pokud se jedná o znak, který není v kontejneru
00413           d1P = delta1Jine;
00414           
00415           ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00416           // vizualizace - posun v algoritmu, nastavení proměnné
00417           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,35));
00418           pomI = new Integer(d1P);
00419           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00420                                                 ABMD.kon.PROM_L,pomI.toString()));
00421         }
00422         i += Math.max(d1P, delta2[j]);  // posun
00423         
00424         pomPosun = Math.max(d1P, delta2[j]);  // uloží hodnotu posunu do pomocné proměnné
00425         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00426         // vizualizace - posun v algoritmu, nastavení proměnných, úprava tabulek
00427         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,36));
00428         pomI = new Integer(i);
00429         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00430                                               ABMD.kon.PROM_I,pomI.toString()));
00431         pomI = new Integer(i+j-1);
00432         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00433                                               ABMD.kon.PROM_IJ,pomI.toString()));
00434         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00435                                               ABMD.kon.PROM_L,""));
00436         posun += pomPosun;  // aktualizuje posun
00437         for (int z = 3*m+presah-1; z >= 0; z--)
00438         {  // posun zvýraznění vpřed
00439           if ((z > (2*m + pomPosun - zvyrazneno - 1)) && (z <= (2*m + pomPosun - 1)))
00440           {  // pokud má být buňka zvýrazněná
00441             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00442                                                   ABMD.kon.TAB_SR,1,z,
00443                                                   ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00444           }
00445           else
00446           {  // pokud buňka nemá být zvýrazněná
00447             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00448                                                   ABMD.kon.TAB_SR,1,z,
00449                                                   ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00450           }
00451         }  // posun zvýraznění vpřed
00452         
00453         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00454         // vizualizace - úprava tabulek
00455         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00456                                               ABMD.kon.TAB_D1,0,pomITD1,
00457                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00458         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00459                                               ABMD.kon.TAB_D1,1,pomITD1,
00460                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00461         for (int z = 0; z < (3*m+presah); z++)
00462         {  // posun v tabulce SR
00463           pom = posun - m + 1 + z;
00464           if (pom <= 0)
00465           {  // pokud je v mezeře před vypisovaným řetězcem
00466             // vyprázdnění obsahu políčka
00467             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00468                                                   ABMD.kon.TAB_SR,1,z,""));
00469           }
00470           else if (pom <= n)
00471           {  // pokud je ve  vypisovaném řetězci
00472             pomC = new Character(text[pom]);
00473             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00474                                                   ABMD.kon.TAB_SR,1,z,pomC.toString()));
00475             vypsano++;  // aktualizace počtu vypsaných znaků
00476           }
00477           else
00478           {  // pokud je za vypisovaným řetězcem
00479             // vyprázdnění obsahu políčka
00480             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00481                                                   ABMD.kon.TAB_SR,1,z,""));
00482           }
00483         }  // posun v tabulce SR
00484         for (int z = 3*m+presah-1; z >= 0; z--)
00485         {  // posun zvýraznění zpět
00486           if ((z >= (2*m - zvyrazneno)) && (z < (2*m)))
00487           {  // pokud má být buňka zvýrazněná
00488             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00489                                                   ABMD.kon.TAB_SR,1,z,
00490                                                   ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00491           }
00492           else
00493           {  // pokud buňka nemá být zvýrazněná
00494             ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00495                                                   ABMD.kon.TAB_SR,1,z,
00496                                                   ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00497           }
00498         }  // posun zvýraznění zpět
00499       }  // pokud řetězec nebyl nalezen
00500     }  // while (i <= (n-m+1))
00501     
00502     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00503     // vizualizace - posun v algoritmu, zrušení zvýraznění, nastavení proměnných
00504     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,39));
00505     for (int z = 0; z < 3*m; z++)
00506     {  // zrušení zvýraznění v tabulce SR
00507       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00508                                             ABMD.kon.TAB_SR,0,z,
00509                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00510       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00511                                             ABMD.kon.TAB_SR,1,z,
00512                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));          
00513     }
00514     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00515                                           ABMD.kon.TAB_D2,0,j+1,
00516                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00517     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00518                                           ABMD.kon.TAB_D2,3,j+1,
00519                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00520     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00521                                           ABMD.kon.PROM_I,""));
00522     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00523                                           ABMD.kon.PROM_J,""));
00524     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00525                                           ABMD.kon.PROM_IJ,""));
00526     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00527                                           ABMD.kon.PROM_MJ,""));
00528     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00529                                           ABMD.kon.PROM_POZ,"-1"));
00530     return -1;  // řetězec nebyl nalezen
00531   }  // public int BMA()
00532 
00533 
00534   /**
00535    * Metoda pro výpočet tabulky delta1
00536    */
00537   private void vypocetDelta1()
00538   {
00539     Integer pomI;  // pomocná proměnná pro vizualizaci
00540     int pom = 1;  // pomocná proměnná pro vizualizaci
00541     int pocet = 2;  // počet sloupců tabulky delta1
00542     int zvyraznenySloupec = 1;  // číslo zvýrazněného sloupce v delta1
00543     
00544     // inicializace kontejneru
00545     delta1 = new TreeMap<Character,Integer>();
00546     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00547      // uloží informace o změně zobrazení - posun v algoritmu, změna rozměrů tabulky delta1
00548     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,44));
00549     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_R,
00550                                           ABMD.kon.TAB_D1,2,pocet));
00551     
00552     // výpočet pole delta1 (pro velký počet možných znaků je zde toto pole
00553     // nahrazeno kontejnerem pro uvedené znaky a proměnnou pro hodnotu
00554     // delta1 neuvedených (jiných) znaků)
00555     for (int i = 1; i <= m; i++)
00556     {  // výpočet delta1
00557       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00558       // zobrazení - zrušení zvýraznění buněk z minulého cyklu
00559       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00560                                             ABMD.kon.TAB_D2,0,pom+1,
00561                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00562       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00563                                             ABMD.kon.TAB_D2,1,pom+1,
00564                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA)); 
00565       
00566       delta1.put(pat[i],(m-i));  // výpočet delta1
00567       
00568       // zobrazení - posun v algoritmu, výpis i, zvýraznění v tabulce delta2, 
00569       // výpis tabulky delta1
00570       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,49));
00571       pomI = new Integer(i);
00572       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00573                                             ABMD.kon.PROM_I,pomI.toString()));
00574       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00575                                             ABMD.kon.TAB_D2,0,i+1,
00576                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00577       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00578                                             ABMD.kon.TAB_D2,1,i+1,
00579                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00580       pom = 1;
00581       pocet = 2;
00582       for (Iterator pomIter = delta1.keySet().iterator(); pomIter.hasNext();)
00583       {  // výpis tabulky delta1
00584         pocet++;  // výpočet počtu sloupců tabulky
00585         Character pismeno = (Character)pomIter.next();
00586         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00587                                               ABMD.kon.TAB_D1,0,pom,pismeno.toString()));
00588         pomI = delta1.get(pismeno);
00589         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00590                                               ABMD.kon.TAB_D1,1,pom,pomI.toString()));
00591         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00592                                               ABMD.kon.TAB_D1,0,pom,
00593                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00594         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00595                                               ABMD.kon.TAB_D1,1,pom,
00596                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00597         if (pat[i] == pismeno)
00598         {  // pokud se má sloupec zvýraznit
00599           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00600                                                 ABMD.kon.TAB_D1,0,pom,
00601                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00602           ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00603                                                 ABMD.kon.TAB_D1,1,pom,
00604                                                 ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00605           zvyraznenySloupec = pom;
00606         }
00607         pom++;  // posun na další sloupec
00608       }  // výpis tabulky delta1
00609       // zvětšení tabulky delta1
00610       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_R,
00611                                             ABMD.kon.TAB_D1,2,pocet));
00612       pom = i;
00613     }  // výpočet delta1
00614     
00615     // uložení informací pro vizualizaci
00616     pocetVDelta1 = pocet;  // počet sloupců tabulky
00617     poziceVDelta1 = new TreeMap<Character,Integer>();  // inicializace kontejneru pro pozice v tabulce
00618     int pomV = 1;
00619     for (Iterator pomIter = delta1.keySet().iterator(); pomIter.hasNext();)
00620     {  // uložení tabulky delta1
00621       Character pismeno = (Character)pomIter.next();
00622       poziceVDelta1.put(pismeno,pomV);
00623       pomV++;
00624     }
00625     
00626     delta1Jine = m;
00627     
00628     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00629     // uloží informace o změně zobrazení - posun v algoritmu, odbarvení zvýraznění, 
00630     // vyprázdnění i, přidání položky pro jiné znaky do delta1
00631     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,51));
00632     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,ABMD.kon.PROM_I,""));
00633     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00634                                           ABMD.kon.TAB_D1,0,zvyraznenySloupec,
00635                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00636     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00637                                           ABMD.kon.TAB_D1,1,zvyraznenySloupec,
00638                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00639     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00640                                           ABMD.kon.TAB_D2,0,pom+1,
00641                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00642     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00643                                           ABMD.kon.TAB_D2,1,pom+1,
00644                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00645     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00646                                           ABMD.kon.TAB_D1,0,pocet-1,ABMD.kon.JINE_ZNAKY));
00647     pomI = new Integer(m);
00648     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00649                                           ABMD.kon.TAB_D1,1,pocet-1,pomI.toString()));
00650   }  // private void vypocetDelta1()
00651 
00652 
00653   /**
00654    * Metoda pro výpočet tabulky delta2
00655    */
00656   private void vypocetDelta2()
00657   {  
00658     Integer pomI;  // pomocná proměnná pro vizualizaci
00659     Character pomC;  // pomocná proměnná pro vizualizaci
00660     int posun = 1;  // pomocná proměnná pro vizualizaci - posun 2. řádku tabulky SR
00661     // nastavení rozměrů tabulky SR pro vizualizaci hledání podřetězců
00662     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_R,
00663                                           ABMD.kon.TAB_SR,2,2*m+1));
00664   
00665     // inicializace polí
00666     delta2 = new int[m+1];
00667     shoda = new int[m+1];
00668     shoda[m] = 0;
00669     
00670     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00671     // uloží informace o změně zobrazení - posun v algoritmu, nastavení shoda[m], obarvení
00672     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,58));
00673     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00674                                           ABMD.kon.TAB_D2,2,m+1,
00675                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00676     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00677                                           ABMD.kon.TAB_D2,2,m+1,"0"));
00678     
00679     delta2[m] = 1;
00680     
00681     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00682     // uloží informace o změně zobrazení - posun v algoritmu, odbarvení shoda[m], 
00683     // nastavení a obarvení delta2[m]
00684     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,59));
00685     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00686                                           ABMD.kon.TAB_D2,2,m+1,
00687                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00688     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00689                                           ABMD.kon.TAB_D2,3,m+1,
00690                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_I));
00691     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00692                                           ABMD.kon.TAB_D2,3,m+1,"1"));
00693     
00694     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00695     // uloží informace o změně zobrazení - posun v algoritmu, odbarvení delta2[m],
00696     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,60));
00697     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00698                                           ABMD.kon.TAB_D2,3,m+1,
00699                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00700      
00701     pomI = new Integer(m); // pomocná proměnná pro převod do řetězce
00702      
00703     for (int j = 0; j <= (m-1); j++)
00704     {
00705       shoda[j] = 1;
00706       delta2[j] = m;
00707       // uloží informace o změně zobrazení - nastavení obsahů buněk (všechny v 1 kroku)
00708       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00709                                             ABMD.kon.TAB_D2,2,j+1,"1"));
00710       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00711                                             ABMD.kon.TAB_D2,3,j+1,pomI.toString()));
00712       // uloží informace o změně zobrazení - obarvení 
00713       // - všechny buňky budou nastaveny v 1 kroku
00714       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00715                                             ABMD.kon.TAB_D2,0,j+1,
00716                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00717       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00718                                             ABMD.kon.TAB_D2,2,j+1,
00719                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00720       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00721                                             ABMD.kon.TAB_D2,3,j+1,
00722                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
00723     }
00724 
00725     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00726     // uloží informace o změně zobrazení - odbarvení 
00727     for (int j = 0; j <= (m-1); j++)
00728     {  // obarvení - všechny buňky budou nastaveny v 1 kroku vizualizace
00729       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00730                                             ABMD.kon.TAB_D2,0,j+1,
00731                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00732       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00733                                             ABMD.kon.TAB_D2,2,j+1,
00734                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00735       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00736                                             ABMD.kon.TAB_D2,3,j+1,
00737                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00738     }
00739     
00740 
00741     // fáze 1: hledání podřetězců shodných s koncem pat
00742     int j = 1;  // index, od kterého se pat kontroluje
00743     
00744     // uloží informace o změně zobrazení - nastaví j a m-j+1, posun v algoritmu, 
00745     // zvýraznění buněk v tabulce
00746     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,65));
00747     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,ABMD.kon.PROM_J,"1"));
00748     pomI = new Integer(m-j+1);
00749     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00750                                           ABMD.kon.PROM_MJ,pomI.toString()));
00751     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00752                                           ABMD.kon.TAB_D2,0,m-j+2,
00753                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00754     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00755                                           ABMD.kon.TAB_D2,1,m-j+2,
00756                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00757     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00758                                           ABMD.kon.TAB_D2,2,m-j+2,
00759                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00760     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00761                                           ABMD.kon.TAB_D2,3,m-j+2,
00762                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00763     
00764     int i = m-1;  // počet shodných znaků
00765     
00766     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00767     pomI = new Integer(i); // pomocná proměnná pro převod do řetězce
00768     // uloží informace o změně zobrazení - nastaví 1 a i-j+1, posun v algoritmu, 
00769     // zvýraznění buněk v tabulce
00770     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,66));
00771     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00772                                           ABMD.kon.PROM_I,pomI.toString()));
00773     pomI = new Integer(i-j+1);
00774     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00775                                           ABMD.kon.PROM_IJ,pomI.toString()));
00776     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00777                                           ABMD.kon.TAB_D2,0,i-j+2,
00778                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00779     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00780                                           ABMD.kon.TAB_D2,1,i-j+2,
00781                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00782     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00783                                           ABMD.kon.TAB_D2,2,i-j+2,
00784                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00785     
00786     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00787     // vizualizace - posun v algoritmu
00788     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,67));
00789     for (int z = 0; z < m; z++)
00790     {  // vizualizace - výpis pat do tabulky SR
00791       pomC = new Character(pat[z+1]);
00792       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00793                                             ABMD.kon.TAB_SR,0,z+1,pomC.toString()));
00794       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00795                                             ABMD.kon.TAB_SR,1,z+1+posun,pomC.toString()));
00796     } 
00797         
00798     while (i >= j)
00799     {
00800       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00801       // vizualizace - posun v algoritmu, úprava zvýraznění buněk v tabulce SR
00802       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,68));
00803       for (int z = 0; z < (2*m+1); z++)
00804       {  // odbarvení buněk
00805         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00806                                               ABMD.kon.TAB_SR,0,z,
00807                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00808         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00809                                               ABMD.kon.TAB_SR,1,z,
00810                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00811       }
00812       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00813                                             ABMD.kon.TAB_SR,0,m-j+1,
00814                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00815       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00816                                             ABMD.kon.TAB_SR,1,i-j+1+posun,
00817                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00818     
00819       while ((i >= j) && (pat[m-j+1] == pat[i-j+1]))
00820       {  // nalezení nejdelší shody
00821         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00822         // vizualizace - posun v algoritmu, odbarvení buněk
00823         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,69));
00824         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00825                                               ABMD.kon.TAB_D2,0,m-j+2,
00826                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00827         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00828                                               ABMD.kon.TAB_D2,1,m-j+2,
00829                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00830         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00831                                               ABMD.kon.TAB_D2,2,m-j+2,
00832                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00833         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00834                                               ABMD.kon.TAB_D2,3,m-j+2,
00835                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00836         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00837                                               ABMD.kon.TAB_D2,0,i-j+2,
00838                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00839         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00840                                               ABMD.kon.TAB_D2,1,i-j+2,
00841                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00842         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00843                                               ABMD.kon.TAB_D2,2,i-j+2,
00844                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00845        
00846         j++;
00847 
00848         // vizualizace - úprava tabulek a proměnných
00849         pomI = new Integer(j);
00850         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00851                                               ABMD.kon.PROM_J,pomI.toString()));
00852         pomI = new Integer(i-j+1);
00853         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00854                                               ABMD.kon.PROM_IJ,pomI.toString()));
00855         pomI = new Integer(m-j+1);
00856         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00857                                               ABMD.kon.PROM_MJ,pomI.toString()));
00858         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00859                                               ABMD.kon.TAB_D2,0,i-j+2,
00860                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00861         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00862                                               ABMD.kon.TAB_D2,1,i-j+2,
00863                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00864         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00865                                               ABMD.kon.TAB_D2,2,i-j+2,
00866                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00867         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00868                                               ABMD.kon.TAB_D2,0,m-j+2,
00869                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));        
00870         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00871                                               ABMD.kon.TAB_D2,1,m-j+2,
00872                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00873         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00874                                               ABMD.kon.TAB_D2,2,m-j+2,
00875                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00876         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00877                                               ABMD.kon.TAB_D2,3,m-j+2,
00878                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00879         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00880                                               ABMD.kon.TAB_SR,0,m-j+1,
00881                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00882         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00883                                               ABMD.kon.TAB_SR,1,i-j+1+posun,
00884                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00885         shoda[i-j+1] = j;
00886         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00887         // vizualizace - posun v algoritmu, úprava tabulek
00888         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,70));
00889         pomI = new Integer(j);
00890         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00891                                               ABMD.kon.TAB_D2,2,i-j+2,pomI.toString()));
00892       }  // while ((i >= j) && ...
00893       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00894       // vizualizace - posun v algoritmu
00895       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,72));
00896       if (j > 1)
00897       {  // pokud byla nalezena shoda, provede aktualizaci
00898         delta2[m-j+1] = Math.min(m-i, delta2[m-j+1]);
00899         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00900         // vizualizace - posun v algoritmu, úprava tabulky
00901         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,73));
00902         pomI = new Integer(delta2[m-j+1]);
00903         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
00904                                               ABMD.kon.TAB_D2,3,m-j+2,pomI.toString()));
00905       }
00906       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00907       // vizualizace - odbarvení zvýrazněných buněk
00908       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00909                                             ABMD.kon.TAB_D2,0,i-j+2,
00910                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00911       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00912                                             ABMD.kon.TAB_D2,1,i-j+2,
00913                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00914       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00915                                             ABMD.kon.TAB_D2,2,i-j+2,
00916                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00917       for (int z = 0; z < (2*m+1); z++)
00918       {  // odbarvení buněk
00919         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00920                                               ABMD.kon.TAB_SR,0,z,
00921                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00922         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00923                                               ABMD.kon.TAB_SR,1,z,
00924                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00925       }
00926       
00927       pomI = new Integer(i);  // původní hodnota i pro posun tabulky
00928       
00929       i = i-j+shoda[m-j+1];
00930       
00931       // vizualizace - posun v algoritmu, úprava tabulek a proměnných
00932       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_P,
00933                                             ABMD.kon.TAB_SR,1,
00934                                             ABMD.kon.POSUN_VPRAVO,pomI-i));
00935       posun += pomI-i;
00936       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,74));
00937       if (i-j+2 > 0)
00938       {  // pokud souřadnice nejsou mimo tabulku
00939         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00940                                               ABMD.kon.TAB_D2,0,i-j+2,
00941                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00942         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00943                                               ABMD.kon.TAB_D2,1,i-j+2,
00944                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00945         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00946                                               ABMD.kon.TAB_D2,2,i-j+2,
00947                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00948       }
00949       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00950                                             ABMD.kon.TAB_SR,0,m-j+1,
00951                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
00952       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00953                                             ABMD.kon.TAB_SR,1,i-j+1+posun,
00954                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
00955 
00956       pomI = new Integer(i);
00957       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00958                                             ABMD.kon.PROM_I,pomI.toString()));
00959       pomI = new Integer(i-j+1);
00960       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
00961                                             ABMD.kon.PROM_IJ,pomI.toString()));
00962       
00963       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
00964       // vizualizace - odbarvení zvýrazněných buněk
00965       if (i-j+2 > 0)
00966       {  // pokud souřadnice nejsou mimo tabulku
00967         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00968                                               ABMD.kon.TAB_D2,0,i-j+2,
00969                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00970         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00971                                               ABMD.kon.TAB_D2,1,i-j+2,
00972                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00973         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00974                                               ABMD.kon.TAB_D2,2,i-j+2,
00975                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00976       }
00977       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00978                                             ABMD.kon.TAB_D2,0,m-j+2,
00979                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00980       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00981                                             ABMD.kon.TAB_D2,1,m-j+2,
00982                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00983       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00984                                             ABMD.kon.TAB_D2,2,m-j+2,
00985                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00986       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00987                                             ABMD.kon.TAB_D2,3,m-j+2,
00988                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00989       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00990                                             ABMD.kon.TAB_SR,0,m-j+1,
00991                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00992       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
00993                                             ABMD.kon.TAB_SR,1,i-j+1+posun,
00994                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
00995       
00996       j = Math.max(shoda[m-j+1],1);
00997       
00998       // vizualizace - posun v algoritmu, úprava tabulek a proměnných
00999       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,75));
01000       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01001                                             ABMD.kon.TAB_D2,0,i-j+2,
01002                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
01003       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01004                                             ABMD.kon.TAB_D2,1,i-j+2,
01005                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
01006       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01007                                             ABMD.kon.TAB_D2,2,i-j+2,
01008                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
01009       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01010                                             ABMD.kon.TAB_D2,0,m-j+2,
01011                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
01012       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01013                                             ABMD.kon.TAB_D2,1,m-j+2,
01014                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
01015       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01016                                             ABMD.kon.TAB_D2,2,m-j+2,
01017                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
01018       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01019                                             ABMD.kon.TAB_D2,3,m-j+2,
01020                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
01021       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01022                                             ABMD.kon.TAB_SR,0,m-j+1,
01023                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_MJ));
01024       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01025                                             ABMD.kon.TAB_SR,1,i-j+1+posun,
01026                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_IJ));
01027       pomI = new Integer(j);
01028       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01029                                             ABMD.kon.PROM_J,pomI.toString()));
01030       pomI = new Integer(i-j+1);
01031       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01032                                             ABMD.kon.PROM_IJ,pomI.toString()));
01033       pomI = new Integer(m-j+1);
01034       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01035                                             ABMD.kon.PROM_MJ,pomI.toString()));
01036     }  // while (i >= j)
01037 
01038     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01039     // vizualizace - odbarvení zvýrazněných buněk, vyprázdnění tabulky SR, 
01040     // vyprázdnění nepotřebných proměnných
01041     for (int z = 0; z < (2*m+1); z++)
01042     {  // odbarvení a vyprázdnění buněk
01043       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01044                                             ABMD.kon.TAB_SR,0,z,
01045                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01046       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01047                                             ABMD.kon.TAB_SR,1,z,
01048                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01049       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
01050                                             ABMD.kon.TAB_SR,0,z,""));
01051       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
01052                                             ABMD.kon.TAB_SR,1,z,""));
01053     }
01054     if (i-j+2 > 0)
01055     {  // pokud souřadnice nejsou mimo tabulku
01056       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01057                                             ABMD.kon.TAB_D2,0,i-j+2,
01058                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01059       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01060                                             ABMD.kon.TAB_D2,1,i-j+2,
01061                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01062       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01063                                             ABMD.kon.TAB_D2,2,i-j+2,
01064                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01065     }
01066     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01067                                           ABMD.kon.TAB_D2,0,m-j+2,
01068                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01069     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01070                                           ABMD.kon.TAB_D2,1,m-j+2,
01071                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01072     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01073                                           ABMD.kon.TAB_D2,2,m-j+2,
01074                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01075     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01076                                           ABMD.kon.TAB_D2,3,m-j+2,
01077                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01078     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01079                                           ABMD.kon.PROM_MJ,""));
01080     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01081                                           ABMD.kon.PROM_IJ,""));
01082 
01083     // fáze 2: výpočet tabulky posunutí
01084     int t = shoda[0];  // délka shodného řetězce s koncem pat
01085     // vizualizace - posun v algoritmu, nastavení proměnné, zvýraznění
01086     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,78));
01087     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01088                                           ABMD.kon.TAB_D2,2,1,
01089                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_T));
01090     pomI = new Integer(shoda[0]);
01091     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01092                                           ABMD.kon.PROM_T,pomI.toString()));
01093 
01094     int L = 1;  // aktuální znak pat
01095     
01096     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01097     // vizualizace - posun v algoritmu, nastavení proměnné, zvýraznění
01098     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,79));
01099     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01100                                           ABMD.kon.TAB_D2,2,1,
01101                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01102     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01103                                           ABMD.kon.PROM_L,"1"));
01104     
01105     int s = 1;  // maximální posunutí úseku, hodnota 1 doplněna pro vizualizaci
01106     while (t > 0)
01107     {
01108       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01109       // vizualizace - odbarvení zvýrazněných buněk
01110       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01111                                             ABMD.kon.TAB_D2,2,s+1,
01112                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01113     
01114       s = m-t+1;
01115       
01116       // vizualizace - posun v algoritmu, nastavení proměnné, zvýraznění
01117       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,82));
01118       pomI = new Integer(s);
01119       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01120                                             ABMD.kon.PROM_S,pomI.toString()));
01121       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01122                                             ABMD.kon.TAB_D2,0,s+1,
01123                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_S));
01124       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01125                                             ABMD.kon.TAB_D2,2,s+1,
01126                                             ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_S));
01127       
01128       for (j = L; j <= s; j++)
01129       {
01130         delta2[j] = Math.min(delta2[j], s);
01131         
01132         ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01133         // vizualizace - posun v algoritmu, úprava proměnné, 
01134         // odbarvení zvýrazněných buněk úprava tabulky, zvýraznění
01135         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,84));
01136         pomI = new Integer(j);
01137         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01138                                               ABMD.kon.PROM_J,pomI.toString()));
01139         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01140                                               ABMD.kon.TAB_D2,0,j,
01141                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01142         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01143                                               ABMD.kon.TAB_D2,3,j,
01144                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01145         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01146                                               ABMD.kon.TAB_D2,0,j+1,
01147                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
01148         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01149                                               ABMD.kon.TAB_D2,3,j+1,
01150                                               ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_J));
01151         pomI = new Integer(delta2[j]);
01152         ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_H,
01153                                               ABMD.kon.TAB_D2,3,j+1,pomI.toString()));
01154       }  // for (j = L; j <= s; j++)
01155       
01156       t = shoda[s];
01157       
01158       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01159       // vizualizace - posun v algoritmu, nastavení proměnné
01160       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,86));
01161       pomI = new Integer(shoda[s]);
01162       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01163                                             ABMD.kon.PROM_T,pomI.toString()));
01164       
01165       L = s+1;
01166       
01167       ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01168       // vizualizace - posun v algoritmu, odbarvení zvýrazněných buněk, nastavení proměnné
01169       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,87));
01170       pomI = new Integer(L);
01171       ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01172                                             ABMD.kon.PROM_L,pomI.toString()));
01173     }  // while (t > 0)
01174 
01175     ABMD.pocetKroku++;  // vytvoření kroku vizualizace
01176     // vizualizace - posun v algoritmu, odbarvení zvýrazněných buněk v tabulkách, 
01177     // vyprázdnění proměnných
01178     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_A_Z,89));
01179     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01180                                           ABMD.kon.TAB_D2,0,j,
01181                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01182     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01183                                           ABMD.kon.TAB_D2,3,j,
01184                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01185     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_T_B,
01186                                           ABMD.kon.TAB_D2,2,s+1,
01187                                           ABMD.kon.BARVA_CERNA,ABMD.kon.BARVA_BILA));
01188     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01189                                           ABMD.kon.PROM_I,""));
01190     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01191                                           ABMD.kon.PROM_J,""));
01192     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01193                                           ABMD.kon.PROM_S,""));
01194     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01195                                           ABMD.kon.PROM_T,""));
01196     ABMD.prubehViz.add(new ZmenaZobrazeni(ABMD.pocetKroku,ABMD.kon.ZM_P,
01197                                           ABMD.kon.PROM_L,""));
01198   }  // private void vypocetDelta2()
01199   
01200 }  // public class Algoritmus
01201 
01202  /*** Konec souboru Algoritmus.java ***/
01203  

Generováno čt 3. bře 2011 13.55:32 pro projekt Aplet pro demonstraci Boyerova-Mooreova algoritmu - programem  doxygen 1.7.1