[61일차] 검색알고리즘 - Naive String Search

서론

오랜만에 다시 검색알고리즘으로 돌아왔다. 오늘은 Naive String Search에 대해서 알아보고자 한다. Naive String Search는 공식 명칭은 아니다. String에서 subString을 찾는 등의 활동에서 많이 사용하는 검색 알고리즘에 강의에서 임의로 이름을 붙인 것이다. 먼저 이 많이 사용되는 방식의 알고리즘을 배운 뒤, 다음 강의에서 더 향상된 KNP알고리즘을 배울 예정이다.

본론

Naive String Search

String에서 subString을 찾을 때 할 수 있는 방법에 무엇이 있을까? 첫번째로 가장 간단한 것은 루프를 이용해 문자열을 순서대로 하나하나 비교하는것이다. 이걸 구현하기 위해서는 중첩 루프가 필요하다.

 function stringSearch(long, short){
 	let count = 0; 
 	for(let i = 0; i<long.length; i++){
    	for(let j = 0; j<short.length; j++)	{
        	if(short[j] !== long[i+j]){
            	//맞지 않으면 루프가 리셋되면서 j가 리셋이 된다.
            	break;
            }
            if(j === short.length - 1 ){
            	count++;
            }
        }
    }
   	return count;
 }

참고

https://www.udemy.com/share/105zfq3@pxNhobIwtiin2DsuRfWs4oThofgo2zJaQtgQhQseie5mO4WSzWjh3JF9Witsg3015g==/