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 , 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
}