알고리즘:[Searching Algorithms] Naive String Search

문제

• loop over the longer string
• loop over the shorter string
• if the characters don't match, break out of the inner loop
• if the characters do match, keep going
• if you complete the inner loop and find a match, increment the count of matches
• Return the count

예시

naiveSearch("lorie loled", "lol") // 1 
naiveSearch("hippopotamus", "po") // 2

풀이

function naiveSearch(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]) break;
	     if(j === short.length-1) count++;
	    }
	 }
	 return count;
}

한 줄 평

• i는 j가 다 돌기 전에 숫자가 올라가지 않으므로short[j]와 long[i+j]를 비교하면서 연속적으로 문자가 계속 일치하는지를 비교할 수 있음
  - short[j] === short[0] // 'p'
  • long[i+j] === long[2] // 'p'
  • short[j] === short[1] // 'o'
  • long[i+j] === long[3] // 'o'
• j를 끝까지 갔는데도 break가 안나온 것은 모든 문자가 일치했다는 뜻이므로 count변수에 +1을 해준다