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.

Kód

    /**
     * Vrati seznam vsech vyskytu daneho vzoru v danem textu v Hammingove vzdalenosti
     * maximalne maxDistance
     * @param text text
     * @param pattern vzor
     * @param maxDistance maximalni vzdalenost (vcetne)
     * @return seznam vsech vyskytu
     */
    public static List<Integer> hammingDistance(String text, String pattern, int maxDistance){
        List<Integer> l = new ArrayList<Integer>();
        int[] first = new int[pattern.length()];
        int[] second = new int[pattern.length()];

        for(int i = 0; i < first.length; i++){
            first[i] = maxDistance + 1; //Hammingova vzdalenost neni definovana
        }

        for(int i = 0; i < text.length(); i++){ //vyplnovani tabulky
            for(int j = 0; j < second.length; j++){
                int prev = 0;
                if(j != 0) prev = first[j-1];
                if(pattern.charAt(j) == text.charAt(i)) second[j] = prev;
                else second[j] = prev + 1;
            }
            if(second[pattern.length() - 1] <= maxDistance) l.add(i);

            //swap columns
            int[] tmp = first;
            first = second;
            second = tmp;
        }
        return l;
    }