Naivní algoritmus vyhledávání v textu

Naivní algoritmus vyhledávání v textu slouží, jak již název napovídá, k vyhledání výskytu daného vzoru v textu. Algoritmus prochází jak text, tak vzor zepředu a porovnává, jestli jsou totožné (na m místech vzoru). Pokud ano, tak byl výskyt nalezen, pokud ne, tak se vzorem posune o jedno místo doprava a postup se opakuje (dokud algoritmus nenarazí na konec textu). Složitost tohoto postupu je O(m \\cdot n), kde m je délka vzoru a n je délka textu.


Kód

    /**
     * Naivni algoritmus vyhledavani vzroru v textu
     * Slozitost: O(m*n)
     * @param text text, ve kterem se bude hledat (delka n)
     * @param pattern vzor, ktery bude hledan (delka m)
     * @return index prvniho znaku prvniho vyskytu vzoru v danem textu, -1 pokud
     * vzor v textu neexistuje
     */
    public static int naiveStringSearchAlgorithm(String text, String pattern){
        if(text.length() == 0 || pattern.length() == 0) return -1;

        OUTER:
        for(int i = 0; i + pattern.length() <= text.length(); i++){
            for(int j = 0; j < pattern.length(); j++){
                if(text.charAt(i + j) != pattern.charAt(j)){
                    continue OUTER;
                }
            }
            return i; //nalezli jsme
        }
        return -1; //nenalezli jsme
    }







Doporučujeme