Hammingova vzdálenost (Hamming distance) dvou řetězců značí, na kolika pozicích se liší. Například dvojice slov pes-les má Hammingovu vzdálenost 1, protože se liší pouze v prvním znaku, dvojice pes-luk má Hammingovu vzdálenost 3, protože se liší na všech třech pozicích.
Vyhledávání podřetězců
Problém nalezení všech podřetězců daného textu, které mají určitou maximální Hammingovu vzdálenost od vzoru, se obvykle řeší dynamickým programováním. Jedná se o stavbu jednoduché tabulky, která má počet řádků stejný jako je délka vzoru a počet sloupců rovný délce prohledávaného textu.
Tabulka se vyplňuje následujícím způsobem. Pokud se vzor a text shodují na pozici (i, j), pak tabulka na této pozici obsahuje stejnou hodnotu, jako na pozici (i-1, j-1), v opačném případě je tato hodnota inkrementována o 1 (tato změna říká, že aby byly řetězce stejné, tak musí dojít k substituci - Hammingova vzdálenost se proto zvyšuje o 1). Řekneme, že daná pozice je výskytem vzoru, pokud je na posledním řádku odpovídajícího sloupce číslo nižší nebo rovné dané vzdálenosti.
Nyní zbývá jen říci, jaké jsou počáteční hodnoty v tabulce. Nultý sloupec tabulky obsahuje nekonečno (nebo jednodušeji hodnotu vyšší, než je maximální povolená vzdálenost), protože značí situaci, kdy ze vstupního řetězce není ještě přečten žádný znak (Hammingova vzálenost není definována pro "oříznutý" podřetězec). Nultý řádek tabulky obsahuje nuly - tímto se definuje, že budou vyhledávány výskyty na všech pozicích.
Příklad
Nalezněte všechny výskyty podřetězce "aaa" v řetězci "bbabababbbb" v Hammingově vzdálenosti 1.
| b | b | a | b | a | b | a | b | b | b | b | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| a | 2 | 3 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| a | 2 | 3 | 4 | 2 | 2 | 1 | 2 | 1 | 2 | 2 | 3 | 3 |
Kód
01./**02. * Vrati seznam vsech vyskytu daneho vzoru v danem textu v Hammingove vzdalenosti03. * maximalne maxDistance04. * @param text text05. * @param pattern vzor06. * @param maxDistance maximalni vzdalenost (vcetne)07. * @return seznam vsech vyskytu08. */09.public static List<Integer> hammingDistance(String text, String pattern, int maxDistance){10. List<Integer> l = new ArrayList<Integer>();11. int[] first = new int[pattern.length()];12. int[] second = new int[pattern.length()];13. 14. for(int i = 0; i < first.length; i++){15. first[i] = maxDistance + 1; //Hammingova vzdalenost neni definovana16. }17. 18. for(int i = 0; i < text.length(); i++){ //vyplnovani tabulky19. for(int j = 0; j < second.length; j++){20. int prev = 0;21. if(j != 0) prev = first[j-1];22. if(pattern.charAt(j) == text.charAt(i)) second[j] = prev;23. else second[j] = prev + 1;24. }25. if(second[pattern.length() - 1] <= maxDistance) l.add(i);26. 27. //swap columns28. int[] tmp = first;29. first = second;30. second = tmp;31. }32. return l;33.}