00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 package boyermooredemo;
00020
00021 import java.awt.Color;
00022
00023
00024
00025
00026
00027
00028 public class Konstanty {
00029
00030 public static final Color BARVA_ZVYRAZNENI_T = new Color(255,255,255);
00031
00032 public static final Color BARVA_ZVYRAZNENI_P = new Color(26,6,153);
00033
00034 public static final Color BARVA_KOMENTARU = new Color(118,118,249);
00035
00036 public static final Color BARVA_TYPU = new Color(46,139,87);
00037
00038 public static final Color BARVA_RIDICICH = new Color(165,42,42);
00039
00040 public static final Color BARVA_LITERALU = new Color(255,59,252);
00041
00042 public static final Color BARVA_CERNA = new Color(0,0,0);
00043
00044 public static final Color BARVA_BILA = new Color(255,255,255);
00045
00046
00047 public static final Color BARVA_I = new Color(99, 255, 99);
00048
00049 public static final Color BARVA_J = new Color(115, 255, 255);
00050
00051 public static final Color BARVA_IJ = new Color(255, 255, 66);
00052
00053 public static final Color BARVA_MJ = new Color(255, 165, 165);
00054
00055 public static final Color BARVA_S = new Color(255, 165, 214);
00056
00057 public static final Color BARVA_T = new Color(198, 198, 255);
00058
00059 public static final Color BARVA_L = new Color(255, 222, 214);
00060
00061 public static final Color BARVA_POZ = new Color(255, 181, 99);
00062
00063
00064 public static final int ZM_T_H = 1;
00065
00066 public static final int ZM_T_B = 2;
00067
00068 public static final int ZM_T_P = 3;
00069
00070 public static final int ZM_T_R = 4;
00071
00072 public static final int ZM_A_B = 5;
00073
00074 public static final int ZM_A_Z = 6;
00075
00076 public static final int ZM_P = 7;
00077
00078 public static final int ZM_N = 8;
00079
00080 public static final int ZM_PO = 9;
00081
00082
00083 public static final int TAB_SR = 1;
00084
00085 public static final int TAB_D1 = 2;
00086
00087 public static final int TAB_D2 = 3;
00088
00089
00090 public static final int PROM_M = 1;
00091
00092 public static final int PROM_N = 2;
00093
00094 public static final int PROM_I = 3;
00095
00096 public static final int PROM_J = 4;
00097
00098 public static final int PROM_IJ = 5;
00099
00100 public static final int PROM_MJ = 6;
00101
00102 public static final int PROM_S = 7;
00103
00104 public static final int PROM_T = 8;
00105
00106 public static final int PROM_L = 9;
00107
00108 public static final int PROM_POZ = 10;
00109
00110
00111 public static final int POPISEK_IJ = 1;
00112
00113 public static final int POPISEK_MJ = 2;
00114
00115 public static final int POPISEK_L = 3;
00116
00117
00118 public static final String TEXTY_POPISKU_IMJ = "i-j+1 = ";
00119
00120 public static final String TEXTY_POPISKU_IPJ = "i+j-1 = ";
00121
00122 public static final String TEXTY_POPISKU_MJ = "m-j+1 = ";
00123
00124 public static final String TEXTY_POPISKU_NM = "n-m+1 = ";
00125
00126 public static final String TEXTY_POPISKU_L = " L = ";
00127
00128 public static final String TEXTY_POPISKU_D1P = "d1P = ";
00129
00130
00131 public static final int POSUN_VLEVO = 0;
00132
00133 public static final int POSUN_VPRAVO = 1;
00134
00135
00136 public static final int[] TAB_SR_VR = {2,36};
00137
00138 public static final int[] TAB_D1_VR = {2,22};
00139
00140 public static final int[] TAB_D2_VR = {4,22};
00141
00142
00143
00144
00145 public static final String[] textyNapovedy = {
00146 "Návod k použití:\n" +
00147 "1. zadejte hledaný řetězec a prohledávaný text\n" +
00148 "2. zahajte vizualizaci kliknutím na tlačítko \"Vpřed\"\n" +
00149 "3. prohlížejte si vizualizaci klikáním na tlačítka \"Vpřed\" a \"Zpět\"\n" +
00150 "4. chcete-li zadat jiný hledaný řetězec, nebo prohledávaný text,\n" +
00151 " klikněte na tlačítko \"Reset\" a upravte řetězce dle potřeby",
00152 "Nyní si můžete prohlížet vizualizaci algoritmu pomocí tlačítek\n" +
00153 "\"Vpřed\" (provede další krok vizualizace) a \"Zpět\" (návrat o 1 krok). \n" +
00154 " Chcete-li změnit vyhledávaný řetězec, nebo prohledávaný text, \n" +
00155 "klikněte na tlačítko \"Reset\", upravte řetězce dle potřeby a znovu\n" +
00156 "spusťte vizualizaci."
00157 };
00158
00159
00160
00161
00162 public static final String[] textyAlgoritmu = {
00163
00164 "private char","[] text; ","// prohledávaný text\n",
00165 "private char","[] pat; ","// hledaný řetězec\n",
00166 "private int ","m; ","// délka hledaného řetězce\n",
00167 "private int ","n; ","// délka prohledávaného textu\n",
00168 "private ","TreeMap<Character,Integer> delta1; ","// kontejner delta1\n",
00169 "private int ","delta1Jine; ","// delta1 pro znaky, které nejsou v kontejneru\n",
00170 "private int","[] delta2;\n",
00171 "private int","[] shoda;\n",
00172 " \n",
00173
00174 "public int"," BMA(String P, String T) {\n",
00175 " // inicializace\n",
00176 " m = P.length(); ","// délka hledaného řetězce\n",
00177 " pat = ","new ","char","[m + ","1","];\n",
00178 " for ","(","int"," i = ","0","; i < m; i++) ","// uloží hledaný řetězec do pole pat\n",
00179 " pat[i+","1","] = P.charAt(i);\n",
00180 " n = T.length(); ","// délka prohledávaného textu\n",
00181 " text = ","new ","char","[n + ","1","];\n",
00182 " for ","(","int ","i = ","0","; i < n; i++) ","// uloží prohledávaný řetězec do pole\n",
00183 " text[i+","1","] = T.charAt(i);\n",
00184 " \n",
00185 " vypocetDelta1(); ","// výpočet tabulky delta1\n",
00186 " vypocetDelta2(); ","// výpočet tabulky delta2\n",
00187 " \n",
00188 " int ","i = ","1","; ","// pozice v textu\n",
00189 " int ","j; ","// pozice v pat\n",
00190 " Integer d1P; ","// pomocná delta1\n",
00191 " while"," (i <= (n-m+","1",")) { \n",
00192 " j = m;\n",
00193 " while ","((j >= ","1",") && (pat[j] == text[i+j-","1","])) ","// dokud do chází ke shodě\n",
00194 " j--; ","// posun na další znak (testuje od konce)\n",
00195 " if ","(j == ","0",") ","// pokud byl řetězec nalezen\n",
00196 " return ","i-","1","; ","// řetězec v poli začíná o 1 dál\n",
00197 " else ","{ ","// pokud řetězec nebyl nalezen\n",
00198 " d1P = delta1.get(text[i+j-","1","]);\n",
00199 " if ","(d1P == ","null",") ","// pokud se jedná o znak, který není v kontejneru\n",
00200 " d1P = delta1Jine;\n",
00201 " i += Math.max(d1P, delta2[j]); ","// posun\n",
00202 " }\n",
00203 " }\n",
00204 " return ","-1","; ","// řetězec nebyl nalezen\n",
00205 "} ","// public int BMA()\n",
00206 " \n",
00207
00208 "private void ","vypocetDelta1() {\n",
00209 " // inicializace kontejneru\n",
00210 " delta1 = ","new ","TreeMap();\n",
00211 " // výpočet pole delta1 (pro velký počet možných znaků je zde toto pole\n",
00212 " // nahrazeno kontejnerem pro uvedené znaky a proměnnou pro hodnotu\n",
00213 " // delta1 neuvedených (jiných) znaků)\n",
00214 " for ","(","int ","i = ","1","; i <= m; i++) { ","// výpočet delta1\n",
00215 " delta1.put(pat[i],(m-i));\n",
00216 " }\n",
00217 " delta1Jine = m;\n",
00218 "} ","// private void vypocetDelta1()\n",
00219 " \n",
00220
00221 "private void ","vypocetDelta2() {\n",
00222 " // inicializace polí\n",
00223 " delta2 = ","new ","int","[m+","1","];\n",
00224 " shoda = ","new ","int","[m+","1","];\n",
00225 " shoda[m] = ","0",";\n",
00226 " delta2[m] = ","1",";\n",
00227 " for ","(","int ","j = ","0","; j <= (m-","1","); j++) {\n",
00228 " shoda[j] = ","1",";\n",
00229 " delta2[j] = m;\n",
00230 " }\n",
00231 " // fáze 1: hledání podřetězců shodných s koncem pat\n",
00232 " int ","j = ","1","; ","// index, od kterého se pat kontroluje\n",
00233 " int ","i = m-","1","; ","// počet shodných znaků\n",
00234 " while ","(i >= j) {\n",
00235 " while ","((i >= j) && (pat[m-j+","1","] == pat[i-j+","1","])) { ","// hlední nejdelší shody\n",
00236 " j++;\n",
00237 " shoda[i-j+","1","] = j;\n",
00238 " }\n",
00239 " if ","(j > ","1",") ","// pokud byla nalezena shoda, provede aktualizaci\n",
00240 " delta2[m-j+","1","] = Math.min(m-i, delta2[m-j+","1","]);\n",
00241 " i = i-j+shoda[m-j+","1","];\n",
00242 " j = Math.max(shoda[m-j+","1","],","1",");\n",
00243 " }\n",
00244 " // fáze 2: výpočet tabulky posunutí\n",
00245 " int ","t = shoda[","0","]; ","// délka shodného řetězce s koncem pat\n",
00246 " int ","L = ","1","; ","// aktuální znak pat\n",
00247 " int ","s; ","// maximální posunutí úseku\n",
00248 " while ","(t > ","0",") {\n",
00249 " s = m-t+","1",";\n",
00250 " for ","(j = L; j <= s; j++) {\n",
00251 " delta2[j] = Math.min(delta2[j], s);\n",
00252 " }\n",
00253 " t = shoda[s];\n",
00254 " L = s+","1",";\n",
00255 " }\n",
00256 "} ","// private void vypocetDelta2()"
00257 };
00258
00259
00260
00261
00262
00263 public static final Color[] barvyAlgoritmu = {
00264
00265 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00266 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00267 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00268 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00269 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00270 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00271 BARVA_TYPU,BARVA_CERNA,
00272 BARVA_TYPU,BARVA_CERNA,
00273 BARVA_CERNA,
00274
00275 BARVA_TYPU,BARVA_CERNA,
00276 BARVA_KOMENTARU,
00277 BARVA_CERNA,BARVA_KOMENTARU,
00278 BARVA_CERNA,BARVA_RIDICICH,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00279 BARVA_RIDICICH,BARVA_CERNA,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00280 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00281 BARVA_CERNA,BARVA_KOMENTARU,
00282 BARVA_CERNA,BARVA_RIDICICH,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00283 BARVA_RIDICICH,BARVA_CERNA,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00284 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00285 BARVA_CERNA,
00286 BARVA_CERNA,BARVA_KOMENTARU,
00287 BARVA_CERNA,BARVA_KOMENTARU,
00288 BARVA_CERNA,
00289 BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00290 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00291 BARVA_CERNA,BARVA_KOMENTARU,
00292 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00293 BARVA_CERNA,
00294 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00295 BARVA_CERNA,BARVA_KOMENTARU,
00296 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00297 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00298 BARVA_RIDICICH,BARVA_CERNA,BARVA_KOMENTARU,
00299 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00300 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00301 BARVA_CERNA,
00302 BARVA_CERNA,BARVA_KOMENTARU,
00303 BARVA_CERNA,
00304 BARVA_CERNA,
00305 BARVA_RIDICICH,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00306 BARVA_CERNA,BARVA_KOMENTARU,
00307 BARVA_CERNA,
00308
00309 BARVA_TYPU,BARVA_CERNA,
00310 BARVA_KOMENTARU,
00311 BARVA_CERNA,BARVA_RIDICICH,BARVA_CERNA,
00312 BARVA_KOMENTARU,
00313 BARVA_KOMENTARU,
00314 BARVA_KOMENTARU,
00315 BARVA_RIDICICH,BARVA_CERNA,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00316 BARVA_CERNA,
00317 BARVA_CERNA,
00318 BARVA_CERNA,
00319 BARVA_CERNA,BARVA_KOMENTARU,
00320 BARVA_CERNA,
00321
00322 BARVA_TYPU,BARVA_CERNA,
00323 BARVA_KOMENTARU,
00324 BARVA_CERNA,BARVA_RIDICICH,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00325 BARVA_CERNA,BARVA_RIDICICH,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00326 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00327 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00328 BARVA_RIDICICH,BARVA_CERNA,BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00329 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00330 BARVA_CERNA,
00331 BARVA_CERNA,
00332 BARVA_KOMENTARU,
00333 BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00334 BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00335 BARVA_RIDICICH,BARVA_CERNA,
00336 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00337 BARVA_CERNA,
00338 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00339 BARVA_CERNA,
00340 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00341 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00342 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00343 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00344 BARVA_CERNA,
00345 BARVA_KOMENTARU,
00346 BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00347 BARVA_TYPU,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,BARVA_KOMENTARU,
00348 BARVA_TYPU,BARVA_CERNA,BARVA_KOMENTARU,
00349 BARVA_RIDICICH,BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00350 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00351 BARVA_RIDICICH,BARVA_CERNA,
00352 BARVA_CERNA,
00353 BARVA_CERNA,
00354 BARVA_CERNA,
00355 BARVA_CERNA,BARVA_LITERALU,BARVA_CERNA,
00356 BARVA_CERNA,
00357 BARVA_CERNA,BARVA_KOMENTARU
00358 };
00359
00360
00361
00362
00363
00364 public static final boolean[] tucneCastiAlgoritmu = {
00365
00366 true,false,false,
00367 true,false,false,
00368 true,false,false,
00369 true,false,false,
00370 true,false,false,
00371 true,false,false,
00372 true,false,
00373 true,false,
00374 false,
00375
00376 true,false,
00377 false,
00378 false,false,
00379 false,true,true,false,false,false,
00380 true,false,true,false,false,false,false,
00381 false,false,false,
00382 false,false,
00383 false,true,true,false,false,false,
00384 true,false,true,false,false,false,false,
00385 false,false,false,
00386 false,
00387 false,false,
00388 false,false,
00389 false,
00390 true,false,false,false,false,
00391 true,false,false,
00392 false,false,
00393 true,false,false,false,
00394 false,
00395 true,false,false,false,false,false,false,
00396 false,false,
00397 true,false,false,false,false,
00398 true,false,false,false,false,
00399 true,false,false,
00400 false,false,false,
00401 true,false,false,false,false,
00402 false,
00403 false,false,
00404 false,
00405 false,
00406 true,false,false,false,
00407 false,false,
00408 false,
00409
00410 true,false,
00411 false,
00412 false,true,false,
00413 false,
00414 false,
00415 false,
00416 true,false,true,false,false,false,false,
00417 false,
00418 false,
00419 false,
00420 false,false,
00421 false,
00422
00423 true,false,
00424 false,
00425 false,true,true,false,false,false,
00426 false,true,true,false,false,false,
00427 false,false,false,
00428 false,false,false,
00429 true,false,true,false,false,false,false,false,
00430 false,false,false,
00431 false,
00432 false,
00433 false,
00434 true,false,false,false,false,
00435 true,false,false,false,false,
00436 true,false,
00437 true,false,false,false,false,false,false,
00438 false,
00439 false,false,false,
00440 false,
00441 true,false,false,false,false,
00442 false,false,false,false,false,
00443 false,false,false,
00444 false,false,false,false,false,
00445 false,
00446 false,
00447 true,false,false,false,false,
00448 true,false,false,false,false,
00449 true,false,false,
00450 true,false,false,false,
00451 false,false,false,
00452 true,false,
00453 false,
00454 false,
00455 false,
00456 false,false,false,
00457 false,
00458 false,false
00459 };
00460
00461
00462
00463
00464
00465 public static final int[][] radkyAlgoritmu = {
00466
00467 {0,2},
00468 {3,5},
00469 {6,8},
00470 {9,11},
00471 {12,14},
00472 {15,17},
00473 {18,19},
00474 {20,21},
00475 {22,22},
00476
00477 {23,24},
00478 {25,25},
00479 {26,27},
00480 {28,33},
00481 {34,40},
00482 {41,43},
00483 {44,45},
00484 {46,51},
00485 {52,58},
00486 {59,61},
00487 {62,62},
00488 {63,64},
00489 {65,66},
00490 {67,67},
00491 {68,72},
00492 {73,75},
00493 {76,77},
00494 {78,81},
00495 {82,82},
00496 {83,89},
00497 {90,91},
00498 {92,96},
00499 {97,101},
00500 {102,104},
00501 {105,107},
00502 {108,112},
00503 {113,113},
00504 {114,115},
00505 {116,116},
00506 {117,117},
00507 {118,121},
00508 {122,123},
00509 {124,124},
00510
00511 {125,126},
00512 {127,127},
00513 {128,130},
00514 {131,131},
00515 {132,132},
00516 {133,133},
00517 {134,140},
00518 {141,141},
00519 {142,142},
00520 {143,143},
00521 {144,145},
00522 {146,146},
00523
00524 {147,148},
00525 {149,149},
00526 {150,155},
00527 {156,161},
00528 {162,164},
00529 {165,167},
00530 {168,175},
00531 {176,178},
00532 {179,179},
00533 {180,180},
00534 {181,181},
00535 {182,186},
00536 {187,191},
00537 {192,193},
00538 {194,200},
00539 {201,201},
00540 {202,204},
00541 {205,205},
00542 {206,210},
00543 {211,215},
00544 {216,218},
00545 {219,223},
00546 {224,224},
00547 {225,225},
00548 {226,230},
00549 {231,235},
00550 {236,238},
00551 {239,242},
00552 {243,245},
00553 {246,247},
00554 {248,248},
00555 {249,249},
00556 {250,250},
00557 {251,253},
00558 {254,254},
00559 {255,256}
00560 };
00561
00562
00563
00564
00565 public static final int[][] blokyAlgoritmu = {
00566 {0,22},
00567 {23,124},
00568 {125,146},
00569 {147,256},
00570 };
00571
00572
00573 public static final int BLOK_DEKLARACE = 0;
00574
00575 public static final int BLOK_BMA = 1;
00576
00577 public static final int BLOK_DELTA1 = 2;
00578
00579 public static final int BLOK_DELTA2 = 3;
00580
00581
00582
00583
00584 public static final int ZADNY_RADEK = 900;
00585
00586
00587
00588
00589 public static final String JINE_ZNAKY = "jiné znaky";
00590
00591
00592
00593
00594
00595 public Konstanty() {
00596 }
00597
00598 }
00599
00600