- 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