JavaScript 알고리즘 (12) Naive Search

 

잊을만하면 계속 돌아오는 알고리즘 포스팅 ✌

오늘 배워본 알고리즘은 pattern searching 알고리즘 중 하나인 Naive Search (문자열 검색 알고리즘) 이다.

 

 

패턴 검색 알고리즘은 문장에서 원하는 문자열을 찾는 알고리즘을 말한다.

전체문자열에서 문자 하나하나 비교해가면서 원하는 단어가 맞는지 확인하는 것이 핵심이다.

Pattern Searching algorithm is string matching algorithm
which is used to find a pattern or a substring in another string.

 

aba 를 찾기 위해 한글자씩 다 돌다리를 두드려본다

 

 

function naiveSearch(long, short){
    var count = 0; // 갯수 초기값 세팅
    
    for(var i = 0; i < long.length; i++){ 	// 전체 텍스트 검사 (A루프)
        for(var j = 0; j < short.length; j++){  // 찾을 텍스트 검사 (B루프)
            
            // A루프 인덱스하나 붙잡고 B루프가 도는동안 맞는 조건을 찾아보자
            if(short[j] !== long[i+j]){	// 찾을텍스트의 문자 !== 전체텍스트 다음순서 인덱스의 문자
                break; 			// 더이상 볼 필요도 없으므로 break!
            }
            
            if(j === short.length - 1){ // 찾을 텍스트의 인덱스 === 전체문자열의 마지막인덱스 (다찾았으면)
                count++; 		// 갯수 +1이(가) 추가 되었습(읍)니다
            }
        }
    }
    return count; // 결과값으로 갯수 리턴
}

naiveSearch("lorie loled", "lol"); // 리턴값은 1